MOAGEZA готує#12283

MOAGEZA готує (Розбір)

Автор задачі:	Мохаммад Нассер (MOAGEZA)
Підготовлено:	Хасан Салех (MathModel)
Редаговано:	Хасан Салех (MathModel)

Рішення

Загальна ідея : Зверніть увагу, що побітове АБО зростає, ми можемо обчислити діапазонне АБО, використовуючи розріджене дерево або сегментне дерево за $O (lo g^{2} n)$ \mathcal{O}(\log^2 n), і ми можемо виконати бінарний пошук у діапазонах та обчислити внески для кожного $(1 \leq k \leq n)$ (1 \le k \le n) відповідно.

Ми будуємо сегментне дерево для діапазонного АБО. Кожен вузол зберігає побітове АБО свого сегмента, тому запит

q (i, r) = j = i ⋁ r a_{j}

q(i,r)=\bigvee_{j=i}^{r} a_j

відповідає за $O (lo g (n))$ .

Для кожного початкового індексу $i$ ми виконуємо два бінарних пошуки по кінцевому індексу $r$ , використовуючи запитане АБО.

Перший пошук знаходить найраніший кінець $ans$ , такий що обидві умови виконуються одночасно:

(q (i, r) & k ~) = 0 та (q (i, r) & k) = k,

(q(i,r)\ \&\ \tilde{k})=0 \qquad\text{та}\qquad (q(i,r)\ \&\ k)=k,

що означає, що жодні заборонені біти поза $k$ не з'явилися, і всі необхідні біти $k$ присутні. Монотонні переміщення: якщо $(q (i, r) & k ~) \neq = 0$ (q(i,r)\ \&\ \tilde{k})\neq 0, то ми занадто далеко і рухаємося вліво; інакше, якщо $(q (i, r) & k) = k$ (q(i,r)\ \&\ k)=k, ми записуємо $r$ і намагаємося скоротити; в іншому випадку ми все ще пропускаємо деякі біти $k$ і рухаємося вправо.

Якщо такий $ans$ не існує, ми пропускаємо цей початок. В іншому випадку ми знаходимо найраніший поганий кінець $stop$ , де вперше з'являється заборонений біт:

(q (i, r) & k ~) \neq = 0.

(q(i,r)\ \&\ \tilde{k})\neq 0.

Завдяки монотонності АБО в $r$ , точно кінці

r \in [ans, stop - 1]

r\in[\mathrm{ans},\ \mathrm{stop}-1]

задовольняють $q (i, r) = k$ q(i,r)=k. Отже, дійсні довжини з початку $i$ є

ℓ \in [ans - i + 1, stop - i] .

\ell \in [\,\mathrm{ans}-i+1,\ \mathrm{stop}-i\,].

Ми додаємо цей інтервал до єдиного глобального масиву різниць $D$ через

D [ℓ_{m i n}] + = 1, D [ℓ_{m a x} + 1] - = 1,

D[\ell_{\min}] {+}{=} 1, \qquad D[\ell_{\max}+1] {-}{=} 1,

потім один префікс по $D$ виводить кількості для всіх розмірів підмасивів $1.. n$ .

Загальна складність $O (n lo g^{2} (n))$ \mathcal{O}(n \log^2(n))

//автор : MathModel
#include <bits/stdc++.h>
using namespace std;
#define int long long

vector<int> tree;
void build(int v,int l,int r,vector<int>&a){
    if(l==r) tree[v]=a[l];
    else{
        int m=(l+r)/2;
        build(v*2,l,m,a);
        build(v*2+1,m+1,r,a);
        tree[v]=tree[v*2]|tree[v*2+1];
    }
}
int query(int v,int l,int r,int ql,int qr){
    if(ql>r||qr<l) return 0;
    if(ql<=l&&r<=qr) return tree[v];
    int m=(l+r)/2;
    return query(v*2,l,m,ql,qr)|query(v*2+1,m+1,r,ql,qr);
}

void solve(){
    int n,x;cin>>n>>x;
    vector<int>a(n);
    for(int i=0;i<n;i++)cin>>a[i];
    tree.assign(4*n,0);
    build(1,0,n-1,a);
    vector<long long>d(n+3,0);
    for(int i=0;i<n;i++){
        int l=i,r=n-1,ans=-1;
        while(l<=r){
            int m=(l+r)/2;
            int q=query(1,0,n-1,i,m);
            if((q & ~x)!=0)r=m-1;         
            else if((q&x)==x){
                ans=m;
                r=m-1;
            }
            else{
                l=m+1;
            }                     
        }
        if(ans>=i){
            int stop=n; l=ans; r=n-1;       
            while(l<=r){
                int m=(l+r)>>1;
                int q=query(1,0,n-1,i,m);
                if((q & ~x)!=0){
                    stop=m;
                    r=m-1;
                }
                else{
                    l=m+1;
                }
            }
            int lmin=ans-i+1,lmax=stop-i; 
            if(lmin<=lmax){
                d[lmin]+=1;
                d[lmax+1]-=1;
            }
        }
    }
    long long cur=0;
    for(int sz=1;sz<=n;sz++){
        cur+=d[sz];
        cout<<cur<<(sz==n?'\n':' ');
    }
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;cin>>T;
    while(T--)solve();
    return 0;
}