【bzoj5312】冒险 - 洛谷保存站

[题面](https://www.lydsy.com/JudgeOnline/problem.php?id=5312)

线段树，势能分析法。

然而我不会势能分析。所以只能口胡一个啦。我们找规律会发现，基本上，区间$and$和区间$or$多了，到了后面这两种操作基本上对答案的影响是差不多的。所以，当区间影响是一样的时候，这两种操作就等价于区间加和区间减，这样就可以做了。然后好像这个复杂度可以通过势能分析，得出是$O(nKlogn)$的，$K$是二进制位数。
如果对复杂度证明感兴趣的话可以去[这里](https://csacademy.com/contest/round-70/task/and-or-max/solution/)。

code:
```
//2018.9.18 by ljz
#include<bits/stdc++.h>
using namespace std;
#define res register int
#define LL long long
#define inf 0x3f3f3f3f
#define eps 1e-15
inline int read(){
    res s=0;
    bool w=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=1;ch=getchar();}
    while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();
    return w?-s:s;
}
inline void _swap(res &x,res &y){
    x^=y^=x^=y;
}
inline int _abs(const res &x){
    return x>0?x:-x;
}
inline int _max(const res &x,const res &y){
    return x>y?x:y;
}
inline int _min(const res &x,const res &y){
    return x<y?x:y;
}
const int N=2e5+10;
namespace MAIN{
    int n,m;
    namespace Segtree{
        struct Segtree{
            int suma,sumo,tag,mx;
        }tr[N<<2];
        inline void pushup(const res &rt){
            res lc=rt<<1,rc=rt<<1|1;
            tr[rt].mx=_max(tr[lc].mx,tr[rc].mx);
            tr[rt].suma=tr[lc].suma&tr[rc].suma;
            tr[rt].sumo=tr[lc].sumo|tr[rc].sumo;
        }
        void build(const res &rt,const res &l,const res &r){
            if(l==r){tr[rt].suma=tr[rt].sumo=tr[rt].mx=read();return;}
            res mid=(l+r)>>1;
            build(rt<<1,l,mid),build(rt<<1|1,mid+1,r);
            pushup(rt);
        }
        inline void change(const res &rt,const res &va){
            tr[rt].suma+=va,tr[rt].sumo+=va,tr[rt].tag+=va,tr[rt].mx+=va;
        }
        inline void pushdown(const res &rt){
            if(!tr[rt].tag)return;
            change(rt<<1,tr[rt].tag),change(rt<<1|1,tr[rt].tag);
            tr[rt].tag=0;
        }
        void modifya(const res &rt,const res &l,const res &r,const res &L,const res &R,const res &va){
            if(l<r)pushdown(rt);
            if((tr[rt].sumo&va)==tr[rt].sumo)return;
            if(L<=l&&r<=R&&(tr[rt].suma&va)-tr[rt].suma==(tr[rt].sumo&va)-tr[rt].sumo){
                change(rt,(tr[rt].suma&va)-tr[rt].suma);
                return;
            }
            res mid=(l+r)>>1;
            if(L<=mid)modifya(rt<<1,l,mid,L,R,va);
            if(R>mid)modifya(rt<<1|1,mid+1,r,L,R,va);
            pushup(rt);
        }
        void modifyo(const res &rt,const res &l,const res &r,const res &L,const res &R,const res &va){
            if(l<r)pushdown(rt);
            if((tr[rt].suma|va)==tr[rt].suma)return;
            if(L<=l&&r<=R&&(tr[rt].suma|va)-tr[rt].suma==(tr[rt].sumo|va)-tr[rt].sumo){
                change(rt,(tr[rt].suma|va)-tr[rt].suma);
                return;
            }
            res mid=(l+r)>>1;
            if(L<=mid)modifyo(rt<<1,l,mid,L,R,va);
            if(R>mid)modifyo(rt<<1|1,mid+1,r,L,R,va);
            pushup(rt);
        }
        int query(const res &rt,const res &l,const res &r,const res &L,const res &R){
            if(l<r)pushdown(rt);
            if(L<=l&&r<=R)return tr[rt].mx;
            res mid=(l+r)>>1,ans=0;
            if(L<=mid)ans=_max(ans,query(rt<<1,l,mid,L,R));
            if(R>mid)ans=_max(ans,query(rt<<1|1,mid+1,r,L,R));
            return ans;
        }
    };
    inline void MAIN(){
        n=read(),m=read();
        Segtree::build(1,1,n);
        for(res i=1;i<=m;i++){
            res opt=read();
            if(opt==1){
                res l=read(),r=read(),va=read();
                Segtree::modifya(1,1,n,l,r,va);
            }
            if(opt==2){
                res l=read(),r=read(),va=read();
                Segtree::modifyo(1,1,n,l,r,va);
            }
            if(opt==3){
                res l=read(),r=read();
                printf("%d\n",Segtree::query(1,1,n,l,r));
            }
        }
    }
}
int main(){
    MAIN::MAIN();
    return 0;
}
```

正在渲染内容...