MOAGEZA yemək bişirir#12283

MOAGEZA yemək bişirir (Həll təhlili)

Problem Müəllifi:	Mohammad Nasser (MOAGEZA)
Hazırlayan:	Hasan Saleh (MathModel)
Redaktə edən:	Hasan Saleh (MathModel)

Həll

Ümumi Fikir : Bitwise OR-un artan olduğunu nəzərə alın, biz aralıq OR-u $O (lo g^{2} n)$ \mathcal{O}(\log^2 n)-də sprase cədvəl və ya seqment ağacı istifadə edərək hesablaya bilərik və biz aralıqlarda ikili axtarış edə bilərik və hər bir $(1 \leq k \leq n)$ (1 \le k \le n) üçün töhfələri müvafiq olaraq hesablaya bilərik.

Biz aralıq OR üçün bir seqment ağacı qururuq. Hər bir düyün öz seqmentinin bitwise OR-un saxlayır, beləliklə bir sorğu

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

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

$O (lo g (n))$ -də cavablandırılır.

Hər bir başlanğıc indeksi $i$ üçün, sorğu edilən OR-u istifadə edərək son indeks $r$ -də iki ikili axtarış edirik.

Birinci axtarış, eyni anda iki şərtin yerinə yetirildiyi ən erkən sonu $ans$ -ı tapır:

(q (i, r) & k ~) = 0 və (q (i, r) & k) = k,

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

yəni $k$ -dan kənarda qadağan olunmuş bitlərin görünmədiyini və $k$ -nın bütün tələb olunan bitlərinin mövcud olduğunu bildirir. Monoton hərəkətlər: əgər $(q (i, r) & k ~) \neq = 0$ (q(i,r)\ \&\ \tilde{k})\neq 0-dirsə, o zaman biz çox irəlidəyik və sola hərəkət edirik; əks halda əgər $(q (i, r) & k) = k$ (q(i,r)\ \&\ k)=k-dirsə, biz $r$ -i qeyd edirik və daha qısa cəhd edirik; əks halda, hələ də $k$ -nın bəzi bitlərini itiririk və sağa hərəkət edirik.

Belə bir $ans$ mövcud deyilsə, bu başlanğıcı atlayırıq. Əks halda, qadağan olunmuş bitin ilk dəfə göründüyü ən erkən pis sonu $stop$ -u tapırıq:

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

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

$r$ -də bitwise monotonluq sayəsində, yalnız aşağıdakı sonlar

r \in [ans, stop - 1]

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

$k$ -ya bərabər olan $q (i, r)$ q(i,r)-ni təmin edir. Buna görə də başlanğıc $i$ -dən etibarlı uzunluqlar

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

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

Bu intervalları bir qlobal fərq cədvəl $D$ -yə əlavə edirik

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

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

sonra $D$ -də bir prefiks bütün alt massiv ölçüləri üçün sayları çıxarır $1.. n$ .

Ümumi mürəkkəblik $O (n lo g^{2} (n))$ \mathcal{O}(n \log^2(n))-dir.

// müəllif : 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;
}