MOAGEZA is cooking#12283

MOAGEZA is cooking (Editorial)

Problem Author:	Mohammad Nasser (MOAGEZA)
Prepared by:	Hasan Saleh (MathModel)
Edited by:	Hasan Saleh (MathModel)

Solution

General Idea : Notice that Bitwise OR is increasing , we can calculate range OR using sprase table or segment tree in $O (lo g^{2} n)$ \mathcal{O}(\log^2 n) and we can binary search in ranges and calculate contributions for each $(1 \leq k \leq n)$ (1 \le k \le n) accordingly.

We build a segment tree for range OR. Each node stores the bitwise OR of its segment, so a query

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

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

is answered in $O (lo g (n))$ .

For every start index $i$ we perform two binary searches on the end index $r$ using the queried OR.

First search finds the earliest end $ans$ such that both conditions hold simultaneously:

(q (i, r) & k ~) = 0 and (q (i, r) & k) = k,

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

meaning no forbidden bits outside $k$ have appeared and all required bits of $k$ are present. The monotone moves are: if $(q (i, r) & k ~) \neq = 0$ (q(i,r)\ \&\ \tilde{k})\neq 0 then we are too far and move left; else if $(q (i, r) & k) = k$ (q(i,r)\ \&\ k)=k we record $r$ and try shorter; otherwise we still miss some bits of $k$ and move right.

If such $ans$ does not exist we skip this start. Otherwise we find the earliest bad end $stop$ where a forbidden bit first appears:

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

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

By OR monotonicity in $r$ , exactly the ends

r \in [ans, stop - 1]

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

satisfy $q (i, r) = k$ q(i,r)=k. Therefore the valid lengths from start $i$ are

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

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

We add this interval to a single global difference array $D$ via

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

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

then one prefix over $D$ outputs the counts for all subarray sizes $1.. n$ .

Overall complexity is $O (n lo g^{2} (n))$ \mathcal{O}(n \log^2(n))

//author : 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;
}