题解：CF2038D Divide OR Conquer
chaeminter2467
·
·
题解
CF2038D Divide OR Conquer
题意
给定一个长度为 n 的序列 a，求分段方式数满足每一段的按位或和不大于后一段的按位或和。
---
### 题解
先有一个比较基础的 dp，设 $dp_{i,s}$ 表示做到第 $i$ 位，最后一段的按位或和为 $s$ 的方案数，转移是朴素的。
显然这个 dp 时空都会爆，分析一下就会发现其有很多无用的状态，如 $a_i > s$，显然 $s$ 就是没用的。
这启示我们分析在固定右端点时，左端点的改变会使 $s$ 拥有多少种取值。具体地，在左端点从右向左推的过程中，按位或不会变小，只会不断有若干位由 $0$ 变为 $1$，所以说 $s$ 的取值种类是 $O(\log V)$ 种的（$V$ 为值域）。
根据上面的分析，会使 $s$ 发生改变的位置也是 $O(\log V)$ 个的，我们把这些位置称为关键位置，记它们从左往右依次为 $l_1,l_2,\cdots,l_k$，分别按位或到当前固定的右端点 $r$ 的值为 $b_1,b_2,\cdots,b_k$。
那么上面那个转移就被我们简化为 $dp_{j,s} \to dp_{r,b_i}(j \in (l_{i-1},l_i] \wedge s \le b_i)$。观察第一维可以得到这个东西可以差分，即我们在 $l_{i-1}$ 处减去 $\sum dp_{s}(s\le b_i)$，再在 $l_i$ 加上这个东西。
所以我们把这些统计操作全都挂在 $l_1,l_2,\cdots,l_k$ 这些位置，再用一个树状数组维护 $ \sum dp_{s}$。这个树状数组具体需要先离散化那些按位或的值再做，不然显然会爆空间。
找关键位置时最多找到 $O(\log V)$ 个，每次通过倍增找，复杂度为 $O(\log n)$，总时间复杂度 $O(n \log n \log V)$。
代码写的有一点点屎，但是尽力加了注释！
**code**
```cpp
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define pb push_back
typedef long long ll;
const int maxn=2e5+5,maxs=21,maxl=33,mod=998244353;
int n,a[maxn],loc[maxl],lg[maxn],tt[maxn];//key location
int s[maxn][maxs],tmp[(maxn*maxl)<<1],len,num=0;
il int qor(int l,int r){int k=lg[r-l+1];return s[l][k]|s[r-(1<<k)+1][k];}
struct qnode{int tp,pos,val;};
int dp[maxn][maxl],idv[maxn][maxl];
vector<qnode> vec[maxn];
il void adt(int &x,int y){x+=y;(x>=mod)&&(x-=mod);}
il int ad(int x,int y){x+=y;return (x>=mod?x-mod:x);}
namespace BIT{
int tr[maxn*maxl];
#define lb(x) ((x)&(-(x)))
il void upd(int x,int val){for(;x<=len;x+=lb(x)) adt(tr[x],val);}
il int qry(int x){int res=0;for(;x;x-=lb(x)) adt(res,tr[x]);return res;}
}using namespace BIT;
il void won(qnode qwq){//做操作
int p=qwq.pos,va=qwq.val,tp=qwq.tp;
int rel=idv[p][va];
if(!tp) adt(dp[p][va],mod-qry(rel));
else adt(dp[p][va],qry(rel));
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n;
for(int i=2;i<=n;i++) lg[i]=lg[i>>1]+1;
for(int i=1;i<=n;i++) cin>>a[i],s[i][0]=a[i];
for(int o=1;o<=20;o++) for(int i=1;i+(1<<o)-1<=n;i++) s[i][o]=s[i][o-1]|s[i+(1<<(o-1))][o-1];
//st表维护位置 i 按位或至 i+2^j-1 的值。
for(int i=1;i<=n;i++){
int va=a[i],pos=i;
while(pos>0){
loc[++tt[i]]=pos;idv[i][tt[i]]=tmp[++num]=va;//找到 l 和 b，idv暂且记录取值，下文离散化部分有具体解释。
for(int o=20;o>=0;o--) if(pos>=(1<<o)&&qor(pos-(1<<o)+1,i)==va) pos-=(1<<o);
if(pos) va=qor(pos,i);
}
loc[tt[i]+1]=0;
for(int j=1;j<=tt[i];j++){
int nw=loc[j],lst=loc[j+1];
vec[nw].pb({1,i,j});vec[lst].pb({0,i,j});
//分别挂在这个关键位置和上一个关键位置，注意代码中的 l 是从大到小的。
}
}
tmp[++num]=0;
sort(tmp+1,tmp+num+1);
len=unique(tmp+1,tmp+num+1)-tmp-1;
for(int i=1;i<=n;i++) for(int j=1;j<=tt[i];j++) idv[i][j]=lower_bound(tmp+1,tmp+len+1,idv[i][j])-tmp;
//离散化，此处 idv 的具体含义为 以 i 为右端点的第 j 种取值在所有数中的排名
upd(1,1);//显然没有任何数时按位或和是 0
for(int i=1;i<=n;i++){
for(qnode j:vec[i]) won(j);
for(int j=1;j<=tt[i];j++){
int rel=idv[i][j];
upd(rel,dp[i][j]);
//以当前为右端点的 dp 值加入树状数组。
}
}
int ans=0;
for(int i=1;i<=tt[n];i++) adt(ans,dp[n][i]);
//统计答案，显然以 n 为右端点的所有取值都有可能。
cout<<ans<<'\n';
return 0;
}
//all for wonyoung
```
---
话说在和同学讨论的时候说到我的st表写法为 $s_{i,j}$ 维护的是 $i$ 按位或到 $i+2^j-1$，这种写法会不会导致凑不出来一些数？（同学说这个是类似斜二进制的东西，但是我不是很理解）能否有大佬解释一下/bx。