专栏文章

题解：CF2038D Divide OR Conquer

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

文章操作

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

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

CF2038D Divide OR Conquer

题意

给定一个长度为 nn 的序列 aa，求分段方式数满足每一段的按位或和不大于后一段的按位或和。
1≤n≤2×105,0≤ai≤1091 \le n \le 2 \times 10^5,0 \le a_i \le 10^9。

题解

先有一个比较基础的 dp，设 dpi,sdp_{i,s} 表示做到第 ii 位，最后一段的按位或和为 ss 的方案数，转移是朴素的。
显然这个 dp 时空都会爆，分析一下就会发现其有很多无用的状态，如 ai>sa_i > s，显然 ss 就是没用的。
这启示我们分析在固定右端点时，左端点的改变会使 ss 拥有多少种取值。具体地，在左端点从右向左推的过程中，按位或不会变小，只会不断有若干位由 00 变为 11，所以说 ss 的取值种类是 O(log⁡V)O(\log V) 种的（VV 为值域）。
根据上面的分析，会使 ss 发生改变的位置也是 O(log⁡V)O(\log V) 个的，我们把这些位置称为关键位置，记它们从左往右依次为 l1,l2,⋯ ,lkl_1,l_2,\cdots,l_k，分别按位或到当前固定的右端点 rr 的值为 b1,b2,⋯ ,bkb_1,b_2,\cdots,b_k。
那么上面那个转移就被我们简化为 dpj,s→dpr,bi(j∈(li−1,li]∧s≤bi)dp_{j,s} \to dp_{r,b_i}(j \in (l_{i-1},l_i] \wedge s \le b_i)。观察第一维可以得到这个东西可以差分，即我们在 li−1l_{i-1} 处减去 ∑dps(s≤bi)\sum dp_{s}(s\le b_i)，再在 lil_i 加上这个东西。
所以我们把这些统计操作全都挂在 l1,l2,⋯ ,lkl_1,l_2,\cdots,l_k 这些位置，再用一个树状数组维护 ∑dps \sum dp_{s}。这个树状数组具体需要先离散化那些按位或的值再做，不然显然会爆空间。
找关键位置时最多找到 O(log⁡V)O(\log V) 个，每次通过倍增找，复杂度为 O(log⁡n)O(\log n)，总时间复杂度 O(nlog⁡nlog⁡V)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表写法为 si,js_{i,j} 维护的是 ii 按位或到 i+2j−1i+2^j-1，这种写法会不会导致凑不出来一些数？（同学说这个是类似斜二进制的东西，但是我不是很理解）能否有大佬解释一下/bx。

评论

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

正在加载评论...