bzoj5312 冒险（势能均摊线段树）

男娘i 2021-12-05 02:17 279阅读 0赞

## 题意： ##

## 给出序列a,每次有一下三种操作。    1，给出l,r,x，将序列l,r之间的所有数都 and x    2，给出l,r,x，将序列l,r之间的所有数都 or x    3，给出l,r，询问l,r之间的最大值 ##

## 第一行包含两个整数 n,m 接下来一行包含 n 个整数, 表示a序列，接下来 m 行, 每行描述了一个操作.    2<=n<=2e5 2<=q<=2e5,0<=ai<=2^20. ##

## 分析：线段树每个节点上维护区间与、区间或和区间最大值。如果一次操作对区间与的影响和对区间或的影响相同，那么就说明对这整个区间的影响都是相同的，就是加上或减去同一个值，直接打标记即可，否则递归下去处理。复杂度是O(nKlogn)的，K是二进制位数，证明在[这里][Link 1]（要翻墙）。做法和代码都和区间整除类似，都是利用运算的性质和线段树的懒标记（区间同时除以一个数和区间位运算一个数）。参考自[https://www.cnblogs.com/zhoushuyu/p/9452012.html][https_www.cnblogs.com_zhoushuyu_p_9452012.html]。照着码了一遍，可以当做板子了。 ##

## 代码： ##

#include<bits/stdc++.h>
    using namespace std;
    int gi(){
        int x=0,w=1;char ch=getchar();
        while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
        if (ch=='-') w=0,ch=getchar();
        while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
        return w?x:-x;
    }
    
    const int N = 2e5+5;
    int n,m,And[N<<2],Or[N<<2],Tag[N<<2],Max[N<<2];
    
    void pushup(int x){
        And[x]=And[x<<1]&And[x<<1|1];Or[x]=Or[x<<1]|Or[x<<1|1];
        Max[x]=max(Max[x<<1],Max[x<<1|1]);
    }
    
    void build(int x,int l,int r){
        if (l==r) {And[x]=Or[x]=Max[x]=gi();return;}
        int mid=l+r>>1;build(x<<1,l,mid);build(x<<1|1,mid+1,r);
        pushup(x);
    }
    
    void cover(int x,int v){
        Tag[x]+=v;And[x]+=v;Or[x]+=v;Max[x]+=v;
    }
    
    void pushdown(int x){
        cover(x<<1,Tag[x]);cover(x<<1|1,Tag[x]);Tag[x]=0;
    }
    
    void mdf_and(int x,int l,int r,int ql,int qr,int v){
        if (l<r) pushdown(x);
        if ((Or[x]&v)==Or[x]) return;
        if (l>=ql&&r<=qr&&(And[x]&v)-And[x]==(Or[x]&v)-Or[x]){
            cover(x,(And[x]&v)-And[x]);return;
        }int mid=l+r>>1;
        if (ql<=mid) mdf_and(x<<1,l,mid,ql,qr,v);
        if (qr>mid) mdf_and(x<<1|1,mid+1,r,ql,qr,v);
        pushup(x);
    }
    void mdf_or(int x,int l,int r,int ql,int qr,int v){
        if (l<r) pushdown(x);
        if ((And[x]|v)==And[x]) return;
        if (l>=ql&&r<=qr&&(And[x]|v)-And[x]==(Or[x]|v)-Or[x]){
            cover(x,(And[x]|v)-And[x]);return;
        }int mid=l+r>>1;
        if (ql<=mid) mdf_or(x<<1,l,mid,ql,qr,v);
        if (qr>mid) mdf_or(x<<1|1,mid+1,r,ql,qr,v);
        pushup(x);
    }
    int query(int x,int l,int r,int ql,int qr){
        if (l<r) pushdown(x);
        if (l>=ql&&r<=qr) return Max[x];
        int mid=l+r>>1,res=0;
        if (ql<=mid) res=max(res,query(x<<1,l,mid,ql,qr));
        if (qr>mid) res=max(res,query(x<<1|1,mid+1,r,ql,qr));
        return res;
    }
    int main(){
        n=gi();m=gi();build(1,1,n);
        while (m--){
            int op=gi(),l=gi(),r=gi(),x;if (op!=3) x=gi();
            if (op==1) mdf_and(1,1,n,l,r,x);
            if (op==2) mdf_or(1,1,n,l,r,x);
            if (op==3) printf("%d\n",query(1,1,n,l,r));
        }
        return 0;
    }

[Link 1]: https://csacademy.com/contest/round-70/task/and-or-max/solution/
[https_www.cnblogs.com_zhoushuyu_p_9452012.html]: https://www.cnblogs.com/zhoushuyu/p/9452012.html