CF1004F Sonya and Bitwise OR（线段树平衡复杂度+or 前缀性质）

CF1004F Sonya and Bitwise OR

有一个长度为 n" role="presentation">n$n$ 的数组 {a}" role="presentation">{a}$\{a\}$，有 m" role="presentation">m$m$ 次操作，又给定一个数 x" role="presentation">x$x$，有两类操作：

• 1 i y 将 ai" role="presentation">ai$a_i$ 改为 y" role="presentation">y$y$；
• 2 l r 查询有多少个区间 [L,R]" role="presentation">[L,R]$[L,R]$ 满足 aL…R" role="presentation">aL…R$a_{L\dots R}$ 的按位或 or" role="presentation">or$\mathtt{o}\mathtt{r}$ 大于等于 x" role="presentation">x$x$。

1≤n,m≤105;0≤ai,x,y≤220" role="presentation">1≤n,m≤105;0≤ai,x,y≤220$1\le n,m\le {10}^5;0\le a_i,x,y\le 2^{20}$。

先考虑如果只有询问操作怎么做。

那可以算出这段区间的中点开始，算出 [l,m]" role="presentation">[l,m]$[l,m]$ 的后缀 or" role="presentation">or$\mathtt{o}\mathtt{r}$ 和 [m+1,r]" role="presentation">[m+1,r]$[m+1,r]$ 的前缀 or" role="presentation">or$\mathtt{o}\mathtt{r}$。

那么可以通过双指针来求出每一个符合条件的区间，如果改为多次询问就用树状数组记下来，一次 log⁡n" role="presentation">logn$\log n$ 查询，总复杂度 nlog⁡n" role="presentation">nlogn$n\log n$。

★Hint" role="presentation">★Hint$★\mathtt{\text{Hint}}$：到这一步之后就一直在想用 CDQ 分治来完成对询问的处理，但其实因为是单点修改，多次询问，可以思考用线段树维护这一过程。而且线段树自带分治功能。

★Trick" role="presentation" style="position: relative;">★Trick$★\mathtt{\text{Trick}}$：一个非常重要的性质，在一段数的 or" role="presentation" style="position: relative;">or$\mathtt{o}\mathtt{r}$ 前缀中，只可能出现 log2⁡a" role="presentation" style="position: relative;">log2a${\log }_{2}a$ 个可能的值。每次最多让一个 0" role="presentation" style="position: relative;">0$0$ 位变成 1" role="presentation" style="position: relative;">1$1$，因此最多只会有 log2⁡a" role="presentation" style="position: relative;">log2a${\log }_{2}a$ 段。

那么可以在线段树中维护区间内的前后缀 or" role="presentation" style="position: relative;">or$\mathtt{o}\mathtt{r}$ 段，每个区间都不会超过 20" role="presentation" style="position: relative;">20$20$ 个，同时记录这个区间内的合法子区间数量，像线段树一样修改询问即可。

总结：

最开始的 CDQ 想法大体方向是正确的，和正解都利用了分治。但是存在修改操作后，对区间分治就不能够在 CDQ 上进行，必须另寻他路。

那么接下来就应当考虑在线解决这个问题，这道题的区间是可以合并的，而平衡复杂度的思想就让我们想到了线段树。

最后这个经典的 Trick" role="presentation" style="position: relative;">Trick$\mathtt{T}\mathtt{r}\mathtt{i}\mathtt{c}\mathtt{k}$ 我不能够熟练使用，下次就知道了。

#define Maxn 100005
int n,m,X;
int a[Maxn];
struct SUB
{
	SUB(int Val=0,int Pl=0,int Pr=0):val(Val),pl(Pl),pr(Pr){}
	int val,pl,pr;
};
SUB tpre[100],tsuf[100];
struct TREE
{
	ll sum;
	vector pre,suf;
	TREE(){ sum=0,pre.clear(),suf.clear(); }
	inline void push(int x,int Nu)
	{
		pre.clear(),suf.clear(),sum=(x>=X),
		pre.pb(SUB(x,Nu,Nu)),suf.pb(SUB(x,Nu,Nu));
	}
}tree[Maxn<<2];
inline TREE merge(TREE L,TREE R)
{
	int ppre=0,psuf=0,tl=L.pre.back().val,tr=R.suf.front().val;
	for(SUB v:L.pre) tpre[++ppre]=v;
	for(SUB v:R.pre) tpre[++ppre]=SUB(v.val|tl,v.pl,v.pr);
	for(SUB v:L.suf) tsuf[++psuf]=SUB(v.val|tr,v.pl,v.pr);
	for(SUB v:R.suf) tsuf[++psuf]=v;
	tpre[ppre+1]=SUB(-1,0,0),tsuf[psuf+1]=SUB(-1,0,0);
	TREE ret; ret.sum=L.sum+R.sum;
	for(int nl=0,nr=0,sl=L.suf.size()-1,sr=R.pre.size()-1;nl<=sl;nl++)
	{
		while(nr<=sr && (L.suf[nl].val|R.pre[nr].val)
		if(nr>sr) break;
		ret.sum+=1ll*(R.pre[sr].pr-R.pre[nr].pl+1)*
			(L.suf[nl].pr-L.suf[nl].pl+1);
	}
	for(int i=2,Last=0;i<=ppre+1;i++) if(tpre[i].val!=tpre[i-1].val)
		assert(tpre[Last+1].val==tpre[i-1].val),
		ret.pre.pb(SUB(tpre[i-1].val,tpre[Last+1].pl,tpre[i-1].pr)),Last=i-1;
	for(int i=2,Last=0;i<=psuf+1;i++) if(tsuf[i].val!=tsuf[i-1].val)
		assert(tsuf[Last+1].val==tsuf[i-1].val),
		ret.suf.pb(SUB(tsuf[i-1].val,tsuf[Last+1].pl,tsuf[i-1].pr)),Last=i-1;
	assert(ret.pre.size()<=30 && ret.suf.size()<=30);
	return ret;
}
void build(int p,int nl,int nr)
{
	if(nl==nr) { tree[p].push(a[nl],nl); return; }
	int mid=(nl+nr)>>1;
	build(p<<1,nl,mid),build(p<<1|1,mid+1,nr);
	tree[p]=merge(tree[p<<1],tree[p<<1|1]);
}
void change(int p,int nl,int nr,int x,int k)
{
	if(nl==nr) { tree[p].push(k,x); return; }
	int mid=(nl+nr)>>1;
	if(mid>=x) change(p<<1,nl,mid,x,k);
	else change(p<<1|1,mid+1,nr,x,k);
	tree[p]=merge(tree[p<<1],tree[p<<1|1]);
}
TREE query(int p,int nl,int nr,int l,int r)
{
	if(nl>=l && nr<=r) return tree[p];
	int mid=(nl+nr)>>1;
	if(mid>=l && mid
		return merge(query(p<<1,nl,mid,l,r),query(p<<1|1,mid+1,nr,l,r));
	else if(mid>=l) return query(p<<1,nl,mid,l,r);
	else return query(p<<1|1,mid+1,nr,l,r);
}
int main()
{
	n=rd(),m=rd(),X=rd();
	for(int i=1;i<=n;i++) a[i]=rd();
	build(1,1,n);
	for(int i=1,opt,x,y;i<=m;i++)
	{
		opt=rd(),x=rd(),y=rd();
		if(opt==1) change(1,1,n,x,y);
		else printf("%lld\n",query(1,1,n,x,y).sum);
	}
	return 0;
}