bzoj

CSAcademy

description

一个序列\(a_i\)，支持区间与一个数，区间或一个数，求区间最大值。

\(n,m\le2\times10^5\)

sol

线段树每个节点上维护区间与、区间或和区间最大值。

如果一次操作对区间与的影响和对区间或的影响相同，那么就说明对这整个区间的影响都是相同的，就是加上或减去同一个值，直接打标记即可，否则递归下去处理。

复杂度是\(O(nK\log n)\)的，\(K\)是二进制位数。

如果对复杂度证明感兴趣的话可以去这里。

code

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

int gi(){

	int x=0,w=1;char ch=getchar();

	while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();

	if (ch=='-') w=0,ch=getchar();

	while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();

	return w?x:-x;

}

const int N = 2e5+5;

int n,m,And[N<<2],Or[N<<2],Tag[N<<2],Max[N<<2];

void pushup(int x){

	And[x]=And[x<<1]&And[x<<1|1];Or[x]=Or[x<<1]|Or[x<<1|1];

	Max[x]=max(Max[x<<1],Max[x<<1|1]);

}

void build(int x,int l,int r){

	if (l==r) {And[x]=Or[x]=Max[x]=gi();return;}

	int mid=l+r>>1;build(x<<1,l,mid);build(x<<1|1,mid+1,r);

	pushup(x);

}

void cover(int x,int v){

	Tag[x]+=v;And[x]+=v;Or[x]+=v;Max[x]+=v;

}

void pushdown(int x){

	cover(x<<1,Tag[x]);cover(x<<1|1,Tag[x]);Tag[x]=0;

}

void mdf_and(int x,int l,int r,int ql,int qr,int v){

	if (l<r) pushdown(x);

	if ((Or[x]&v)==Or[x]) return;

	if (l>=ql&&r<=qr&&(And[x]&v)-And[x]==(Or[x]&v)-Or[x]){

		cover(x,(And[x]&v)-And[x]);return;

	}int mid=l+r>>1;

	if (ql<=mid) mdf_and(x<<1,l,mid,ql,qr,v);

	if (qr>mid) mdf_and(x<<1|1,mid+1,r,ql,qr,v);

	pushup(x);

}

void mdf_or(int x,int l,int r,int ql,int qr,int v){

	if (l<r) pushdown(x);

	if ((And[x]|v)==And[x]) return;

	if (l>=ql&&r<=qr&&(And[x]|v)-And[x]==(Or[x]|v)-Or[x]){

		cover(x,(And[x]|v)-And[x]);return;

	}int mid=l+r>>1;

	if (ql<=mid) mdf_or(x<<1,l,mid,ql,qr,v);

	if (qr>mid) mdf_or(x<<1|1,mid+1,r,ql,qr,v);

	pushup(x);

}

int query(int x,int l,int r,int ql,int qr){

	if (l<r) pushdown(x);

	if (l>=ql&&r<=qr) return Max[x];

	int mid=l+r>>1,res=0;

	if (ql<=mid) res=max(res,query(x<<1,l,mid,ql,qr));

	if (qr>mid) res=max(res,query(x<<1|1,mid+1,r,ql,qr));

	return res;

}

int main(){

	n=gi();m=gi();build(1,1,n);

	while (m--){

		int op=gi(),l=gi(),r=gi(),x;if (op!=3) x=gi();

		if (op==1) mdf_and(1,1,n,l,r,x);

		if (op==2) mdf_or(1,1,n,l,r,x);

		if (op==3) printf("%d\n",query(1,1,n,l,r));

	}

	return 0;

}