BZOJ5312 冒险

神奇线段树，理论复杂度分析白学系列…… 先粘代码…… ```C #include<cstdio> #include<algorithm> using namespace std;const int N=2*1e5+10;int a[N];int n;int m; struct linetree { int val[4*N];int san[4*N];int sor[4*N];int sev[4*N]; inline void ud(int p) {val[p]=max(val[p<<1],val[p<<1|1]);san[p]=san[p<<1]&san[p<<1|1];sor[p]=sor[p<<1]|sor[p<<1|1];} inline void pd(int p) { if(sev[p]==-1)return; val[p<<1|1]=san[p<<1|1]=sor[p<<1|1]=sev[p<<1|1]=sev[p]; val[p<<1]=san[p<<1]=sor[p<<1]=sev[p<<1]=sev[p];sev[p]=-1; } inline void build(int p,int l,int r) { sev[p]=-1;if(r-l==1){val[p]=san[p]=sor[p]=a[r];return;}int mid=(l+r)/2; build(p<<1,l,mid);build(p<<1|1,mid,r);ud(p); } inline void setad(int p,int l,int r,int dl,int dr,int ad) { if(dl==l&&dr==r&&(san[p]&ad)==(sor[p]&ad)){val[p]=sev[p]=sor[p]=san[p]=san[p]&ad;return;} int mid=(l+r)/2;pd(p); if(dl<mid)setad(p<<1,l,mid,dl,min(dr,mid),ad); if(mid<dr)setad(p<<1|1,mid,r,max(dl,mid),dr,ad);ud(p); } inline void setro(int p,int l,int r,int dl,int dr,int ro) { if(dl==l&&dr==r&&(san[p]|ro)==(sor[p]|ro)){val[p]=sev[p]=sor[p]=san[p]=san[p]|ro;return;} int mid=(l+r)/2;pd(p); if(dl<mid)setro(p<<1,l,mid,dl,min(dr,mid),ro); if(mid<dr)setro(p<<1|1,mid,r,max(dl,mid),dr,ro);ud(p); } inline int qmx(int p,int l,int r,int dl,int dr) { if(dl==l&&dr==r){return val[p];} pd(p);int mid=(l+r)/2;int res=0; if(dl<mid)res=max(res,qmx(p<<1,l,mid,dl,min(dr,mid))); if(mid<dr)res=max(res,qmx(p<<1|1,mid,r,max(dl,mid),dr));return res; } }lt; int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++)scanf("%d",&a[i]);lt.build(1,0,n); for(int i=1,t,l,r,x;i<=m;i++) { scanf("%d%d%d",&t,&l,&r); switch(t) { case 1:{scanf("%d",&x);lt.setad(1,0,n,l-1,r,x);break;} case 2:{scanf("%d",&x);lt.setro(1,0,n,l-1,r,x);break;} case 3:{printf("%d\n",lt.qmx(1,0,n,l-1,r));break;} } }return 0; } ```