题解：CF2038D Divide OR Conquer

· · 题解

CF2038D Divide OR Conquer

我咋这么菜！

一个比较好理解，但实现没有那么简洁的做法。

solution

可以用 st 表维护区间或值，复杂度 O(n\log n)-O(1)。

设 dp_{i,s} 表示当前考虑了前 i 位，最后一段的异或和为 s。转移是容易的。

然而这样光状态数就是 O(nV) 的，先考虑减少状态。

显然，最后一段一定包含 i。对于一段固定 r，l 不断减小的后缀异或和，已经变为 1 的位置不可能再变为 0。也就是说，对于每个 i，s 只有 O(\text{popcount}(a_i)) 种合法取值。所以总的合法状态数就是 O(n\log V) 的。

接着优化转移。对于一个 (i,s)，考虑哪些 (k,s') 可以转移到它。根据上文分析，后缀异或值随着 l 的减小变大的位置个数是 O(\log V) 的，于是对于每一种合法异或值 val_{i,j}，找出 l 的范围 [L_j,R_j]。这个位置可以二分找出。（具体来说，每次找到最远的 pos 使得 \text{OR}(pos,i) 不变，那么 pos-1 就是一个“断点”。）

那么当 (k,s') 满足 k\in [L_j-1,R_j-1],s'\le s（因为 l 是被分进最后一段，所以应该从 l-1 转移。）时，有 dp_{k,s'}\to dp_{i,s}。这个东西一看就是主席树可以维护的形式，所以上主席树。……？

别急。注意到 dp 顺序显然是按 i 从小到大，所以可以把查询挂在查询端点上离线处理。这时候只需要对于 s 这一维单点加，查询前缀和，树状数组即可。

复杂度 O(n\log V\log n+n\log (n\log V))。

code

写的有点混乱邪恶。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define mkp make_pair
#define fi first
#define se second
#define eb emplace_back
const int maxn=200004,maxl=32,mxl=20,Maxn=maxn*31,mod=998244353;
void adt(int &x,int y){x+=y,(x>=mod)&&(x-=mod);}
int ad(int x,int y){return x+=y,(x>=mod)?(x-mod):x;}
int n;
int a[maxn];
int pw[maxl],lg[maxn],o[maxn][maxl]; 
void oinit(){
    pw[0]=1;for(int i=1;i<=mxl;i++) pw[i]=pw[i-1]<<1;
    for(int i=2;i<=n;i++) lg[i]=lg[i>>1]+1;
    for(int i=1;i<=n;i++) o[i][0]=a[i];
    for(int j=1;j<=mxl;j++) for(int i=1;i+pw[j]-1<=n;i++)
        o[i][j]=o[i][j-1]|o[i+pw[j-1]][j-1];
}
inline int qry(int L,int R){//O(1) 查询区间或值 
    int k=lg[R-L+1];
    return o[L][k]|o[R-pw[k]+1][k];
}
int b[Maxn],len;
int liz[maxn],val[maxn][maxl];
vector <pii> vec[maxn];
void sol(int Pos){//找断点 
    int pos=Pos,v=a[Pos];
    vec[Pos-1].eb(mkp(Pos,1));
    while(pos){
        b[++len]=v,val[Pos][++liz[Pos]]=v;
        int l=1,r=pos,md;
        while(l<r){md=(l+r>>1);(qry(md,Pos)==v)?(r=md):(l=md+1);}
        pos=l;if(pos==1) break;
        v|=a[--pos];
        vec[pos-1].eb(mkp(Pos,-liz[Pos]));
        vec[pos-1].eb(mkp(Pos,liz[Pos]+1));
        //将查询挂在左右端点上 
    }
}
int dp[maxn][maxl];
namespace BIT{
    int tr[Maxn];
    inline void Add(int i,int x){for(;i<=len;i+=i&-i) adt(tr[i],x);}
    inline int Qry(int i){int res=0;for(;i;i&=i-1) adt(res,tr[i]);return res;}
}using namespace BIT;
int ans;
void DP(){
    b[++len]=0;sort(b+1,b+1+len);len=unique(b+1,b+1+len)-(b+1);
    val[0][++liz[0]]=0,dp[0][1]=1;
    for(int i=0;i<=n;i++) for(int j=1;j<=liz[i];j++) val[i][j]=lower_bound(b+1,b+1+len,val[i][j])-b;
    for(int i=0;i<n;i++){
        for(int j=1;j<=liz[i];j++) Add(val[i][j],dp[i][j]);
        for(pii o:vec[i]){
            if(o.se<0){o.se=-o.se;adt(dp[o.fi][o.se],mod-Qry(val[o.fi][o.se]));}
            else{adt(dp[o.fi][o.se],Qry(val[o.fi][o.se]));}
        }
    }
    for(int j=1;j<=liz[n];j++) adt(ans,dp[n][j]);
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    oinit();
    for(int i=1;i<=n;i++) sol(i);
    DP();
    cout<<ans<<'\n';
    return 0;
}