记录编号	494465	评测结果	AAAAAAAAAA
题目名称	数列操作ψ	最终得分	100
用户昵称	CSU_Turkey	是否通过	通过
代码语言	C++	运行时间	2.989 s
提交时间	2018-04-11 16:22:01	内存使用	4.38 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;
void rd(int &x){
	x=0;int f=1;char ch=getchar();
	while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch<='9' && ch>='0')x=x*10+ch-'0',ch=getchar();
	x*=f;
}

#define ls o<<1
#define rs o<<1|1
#define mid (l+r>>1)

const int inf=1e5+10;
const int INF=0x7fffffff;
int n,m;
int mx[inf<<2],same[inf<<2],add[inf<<2];

void upd(int o){mx[o]=max(mx[ls],mx[rs]);same[o]=(same[ls]&same[rs])&(~(mx[ls]^mx[rs]));}

void build(int l,int r,int o){
	if(l==r){rd(mx[o]);same[o]=INF;}
	else {build(l,mid,ls);build(mid+1,r,rs);upd(o);}
}

void modify(int o,int x){mx[o]+=x;add[o]+=x;}

void tagdown(int o){modify(ls,add[o]);modify(rs,add[o]);add[o]=0;}

void modify_and(int l,int r,int o,int L,int R,int x){
	if(l>=L && r<=R && (((x^INF)&same[o])==(x^INF)))modify(o,(mx[o]&x)-mx[o]);
	else {
		tagdown(o);
		if(mid>=L)modify_and(l,mid,ls,L,R,x);
		if(mid<R)modify_and(mid+1,r,rs,L,R,x);
		upd(o);
	}
}

void modify_or(int l,int r,int o,int L,int R,int x){
	if(l>=L && r<=R && ((x&same[o])==x))modify(o,(mx[o]|x)-mx[o]);
	else {
		tagdown(o);
		if(mid>=L)modify_or(l,mid,ls,L,R,x);
		if(mid<R)modify_or(mid+1,r,rs,L,R,x);
		upd(o);
	}
}

int query(int l,int r,int o,int L,int R){
	if(l>=L && r<=R)return mx[o];
	else {
		int ans=0;tagdown(o);
		if(mid>=L)ans=max(ans,query(l,mid,ls,L,R));
		if(mid<R)ans=max(ans,query(mid+1,r,rs,L,R));
		return ans;
	}
}

int main(){
	freopen("series_wei.in","r",stdin);
	freopen("series_wei.out","w",stdout);
	rd(n);rd(m);
	build(1,n,1);
	for(int i=1;i<=m;i++){
		int opt,l,r,val;
		rd(opt);rd(l);rd(r);
		if(opt!=3)rd(val);
		if(opt==1)modify_and(1,n,1,l,r,val);
		if(opt==2)modify_or(1,n,1,l,r,val);
		if(opt==3)printf("%d\n",query(1,n,1,l,r));
	}
	return 0;
}