题解：CF2038D Divide OR Conquer

· · 题解

arc 出了类似题，来点垃圾做法。

首先注意到以一个位置结尾的后缀 or 的结果只有 O(\log v) 种，理由是每个二进制位只有变成 1 时可能贡献一个变化点。我们可以通过每个二进制位上一个为 1 的位置来找到这些变化点。

设 f_{i,j} 表示以 i 结尾的段的 or 值是 j 的方案数。转移形如 f_{i,j}=\sum_{k=l}^r\sum_{v=0}^jf_{k,v}，直接数据结构维护要单点修改二维数点，有 O(n\log v) 个查询，只能 O(n\log^2v\log n)，无法通过。（当然这个题的信息可以差分，所以能用主席树维护，但是空间可能无法承受）

但是注意到这些由变化点划分出的段只会在末尾加一段，或者合并相邻两个段，于是我们上一个线段树合并就可以做到 O(n\log^2v) 了。具体地，某个点删掉时把以它结尾的段的线段树合并到下一个段上。

但是空间也是 O(n\log^2v)，需要卡常。考虑如果 f_{i,j}=0 就不修改，并在线段树合并时把重复出现过的节点回收掉就可以通过了。

#include <bits/stdc++.h>
#define ll long long
#define mid (l+r>>1)
using namespace std;
const int mod=998244353;
int n,a[200005],lst[35],rt[200005],stk[35],b[35],ctt,tong[10000000],tr[30000000],ls[30000000],rs[30000000],tp,tot;
int newnode(){
    return ctt?tong[--ctt]:++tot;
}
void upd(int &p,int l,int r,int pos,int v){
    if(!p) p=newnode(),tr[p]=ls[p]=rs[p]=0;
    tr[p]=(tr[p]+v)%mod;
    if(l==r) return ;
    pos<=mid?upd(ls[p],l,mid,pos,v):upd(rs[p],mid+1,r,pos,v);
}
int merge(int x,int y,int l,int r){
    if(!x) return y;
    if(!y) return x;
    tr[x]=(tr[x]+tr[y])%mod;
    if(ctt<10000000) tong[ctt++]=y;
    if(l==r) return x;
    return ls[x]=merge(ls[x],ls[y],l,mid),rs[x]=merge(rs[x],rs[y],mid+1,r),x;
}
int query(int p,int l,int r,int lt,int rt){
    if(!p) return 0;
    if(lt<=l&&r<=rt) return tr[p];
    int res=0;
    if(lt<=mid) res=(res+query(ls[p],l,mid,lt,rt))%mod;
    if(rt>mid) res=(res+query(rs[p],mid+1,r,lt,rt))%mod;
    return res;
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        int now=a[i],tt=0;
        b[++tt]=i;
        for(int j=1;j<=tp;now|=a[stk[j]],j++)
            if((now&a[stk[j]])!=a[stk[j]])
                b[++tt]=stk[j];
            else rt[b[tt]]=merge(rt[b[tt]],rt[stk[j]],0,1<<30);
        for(int j=1,k=0;j<=tt;j++){
            k|=a[b[j]];
            int vl=query(rt[b[j]],0,1<<30,0,k)+(j==tt);
            if(vl>0) upd(rt[i+1],0,1<<30,k,vl);
        }
        tp=tt,memcpy(stk,b,sizeof(b));
    }
    cout<<tr[rt[n+1]]%mod<<'\n';
    return 0;
}