专栏文章

题解：CF2038D Divide OR Conquer

qqyy_
CF2038D题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@mimz92id
此快照首次捕获于
2025/12/01 17:59
3 个月前
此快照最后确认于
2025/12/01 17:59
3 个月前
查看原文

CF2038D Divide OR Conquer

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

solution

可以用 st 表维护区间或值，复杂度 O(nlog⁡n)−O(1)O(n\log n)-O(1)。
设 dpi,sdp_{i,s} 表示当前考虑了前 ii 位，最后一段的异或和为 ss。转移是容易的。
然而这样光状态数就是 O(nV)O(nV) 的，先考虑减少状态。
显然，最后一段一定包含 ii。对于一段固定 rr，ll 不断减小的后缀异或和，已经变为 11 的位置不可能再变为 00。也就是说，对于每个 ii，ss 只有 O(popcount(ai))O(\text{popcount}(a_i)) 种合法取值。所以总的合法状态数就是 O(nlog⁡V)O(n\log V) 的。
接着优化转移。对于一个 (i,s)(i,s)，考虑哪些 (k,s′)(k,s') 可以转移到它。根据上文分析，后缀异或值随着 ll 的减小变大的位置个数是 O(log⁡V)O(\log V) 的，于是对于每一种合法异或值 vali,jval_{i,j}，找出 ll 的范围 [Lj,Rj][L_j,R_j]。这个位置可以二分找出。（具体来说，每次找到最远的 pospos 使得 OR(pos,i)\text{OR}(pos,i) 不变，那么 pos−1pos-1 就是一个“断点”。）
那么当 (k,s′)(k,s') 满足 k∈[Lj−1,Rj−1],s′≤sk\in [L_j-1,R_j-1],s'\le s（因为 ll 是被分进最后一段，所以应该从 l−1l-1 转移。）时，有 dpk,s′→dpi,sdp_{k,s'}\to dp_{i,s}。这个东西一看就是主席树可以维护的形式，所以上主席树。……？
别急。注意到 dp 顺序显然是按 ii 从小到大，所以可以把查询挂在查询端点上离线处理。这时候只需要对于 ss 这一维单点加，查询前缀和，树状数组即可。
复杂度 O(nlog⁡Vlog⁡n+nlog⁡(nlog⁡V))O(n\log V\log n+n\log (n\log V))。

code

写的有点混乱邪恶。
CPP
#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;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...