题目链接：

　　

Solution

　　用jry推荐的写法即可做到单次$O(log^{2}N)$，不过随机数据下表现非常优秀。

　　$log^{2}$大概就是一共$log$位，然后每位$O(N)$级的，所以一共$NlogN$段，每段在线段树上又是$log$。

　　jls给的详细证明就是说，每位单独考虑形成一个01串，势能函数就是每位差分后的$1$的个数，太详细的啥我也不是很熟练了..要是有路过的大神能详细讲一下咩QwQ

　　具体的就是维护一个区间的$same$，其二进制下01的意义表示区间中所有数的二进制位第$k$位是否相同。

　　处理标记，当整个区间的 需要修改 的二进制位相同时即可直接打上标记。

　　然后就是正常搞了啊..其实当满足上述的情况后修改就可以变成区间加减标记来处理了，只需要一个标记即可，常数会更优一点。

Code：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;inline int read(){	int x=0,f=1; char ch=getchar();	while (ch<'0' || ch>'9') {if (ch=='-') f=-1; ch=getchar();}	while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();}	return x*f;}#define MAXN 100010int N,M,a[MAXN];#define AllSame ((1<<30)-1)struct SgtNode{	int l,r,otag,atag,same,maxx;}tree[MAXN<<2];inline void Update(const int &now) {	tree[now].maxx=max(tree[now<<1].maxx,tree[now<<1|1].maxx);	tree[now].same=( tree[now<<1].same & tree[now<<1|1].same ) & ( tree[now<<1].maxx ^ (~tree[now<<1|1].maxx) );}inline void Build(const int &now,const int &l,const int &r){	tree[now].l=l; tree[now].r=r;	tree[now].otag=0; tree[now].atag=AllSame;	if (l==r) {		tree[now].maxx=a[l]; tree[now].same=AllSame;		return;	}	int mid=(l+r)>>1;	Build(now<<1,l,mid); Build(now<<1|1,mid+1,r);	Update(now);}inline void And(const int &now,const int &val) {tree[now].maxx&=val; tree[now].otag&=val; tree[now].atag&=val;}inline void Or(const int &now,const int &val) {tree[now].maxx|=val; tree[now].otag|=val; tree[now].atag|=val;}inline void Pushdown(const int &now){	if (tree[now].l==tree[now].r || (!tree[now].otag && tree[now].atag==AllSame)) return;	int ot=tree[now].otag,at=tree[now].atag;	tree[now].otag=0; tree[now].atag=AllSame;	if (ot) Or(now<<1,ot),Or(now<<1|1,ot);	if (at!=AllSame) And(now<<1,at),And(now<<1|1,at);}inline bool CheckOr(const int &same,const int &val) {return (same&val)==val;}inline void ModifyOr(const int &now,const int &L,const int &R,const int &val){	int l=tree[now].l,r=tree[now].r;	if (L>r || R
          
           =r && CheckOr(tree[now].same,val)) { Or(now,val); return; } Pushdown(now); ModifyOr(now<<1,L,R,val); ModifyOr(now<<1|1,L,R,val); Update(now);}inline bool CheckAnd(const int &same,const int &val) {return (~same&AllSame|val)==val;}inline void ModifyAnd(const int &now,const int &L,const int &R,const int &val){ int l=tree[now].l,r=tree[now].r; if (L>r || R
           
            =r && CheckAnd(tree[now].same,val)) { And(now,val); return; } Pushdown(now); ModifyAnd(now<<1,L,R,val); ModifyAnd(now<<1|1,L,R,val); Update(now);}inline int Query(const int &now,const int &L,const int &R){ int l=tree[now].l,r=tree[now].r; if (L<=l && R>=r) { return tree[now].maxx; } Pushdown(now); int mid=(l+r)>>1,re=0; if (L<=mid) re=Query(now<<1,L,R); if (R>mid) re=max(re,Query(now<<1|1,L,R)); return re;}int main(){ freopen("series_wei.in","r",stdin); freopen("series_wei.out","w",stdout); N=read(),M=read(); for (int i=1; i<=N; i++) a[i]=read(); Build(1,1,N); while (M--) { int opt=read(),l=read(),r=read(),val; switch (opt) { case 1: val=read(); ModifyAnd(1,l,r,val); break; case 2: val=read(); ModifyOr(1,l,r,val); break; case 3: printf("%d\n",Query(1,l,r)); break; } } return 0;}/*8 64 0 5 7 2 9 12 82 2 5 151 3 5 23 5 71 5 7 122 1 6 43 2 6*/