题解：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

就不修改，并在线段树合并时把重复出现过的节点回收掉就可以通过了。

CPP

#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;
}

题解：CF2038D Divide OR Conquer

文章操作

相关推荐

评论

题解：CF2038D Divide OR Conquer