题目链接：
http://cogs.pro/cogs/problem/problem.php?pid=2638
Solution
用jry推荐的写法即可做到单次$O(log^{2}N)$，不过随机数据下表现非常优秀。
$log^{2}$大概就是一共$log$位，然后每位$O(N)$级的，所以一共$NlogN$段，每段在线段树上又是$log$。
jls给的详细证明就是说，每位单独考虑形成一个01串，势能函数就是每位差分后的$1$的个数，太详细的啥我也不是很熟练了..要是有路过的大神能详细讲一下咩QwQ
具体的就是维护一个区间的$same$，其二进制下01的意义表示区间中所有数的二进制位第$k$位是否相同。
处理标记，当整个区间的 需要修改 的二进制位相同时即可直接打上标记。
然后就是正常搞了啊..其实当满足上述的情况后修改就可以变成区间加减标记来处理了，只需要一个标记即可，常数会更优一点。
Code：
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
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 100010 int 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<l) return;
if (L<=l && 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<l) return;
if (L<=l && 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 6
4 0 5 7 2 9 12 8
2 2 5 15
1 3 5 2
3 5 7
1 5 7 12
2 1 6 4
3 2 6
*/