【线段树应用】XOR的艺术

迷南。 2024-03-25 21:13 38阅读 0赞

**lazy tag的应用**

[P2574 XOR的艺术 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)][P2574 XOR_ - _ _ _ _luogu.com.cn]

题意：

![e3255225ca917fa18b225a6c919fb53e.png][]

思路：

1.  答案需要我们维护区间cnt

1.  考虑修改操作对区间cnt的影响：就是区间长度-cnt

1.  考虑pushdown怎么写：就是两个子区间的区间长度-cnt

但是在写pushdown的时候，有个很重要的点就是：每次pushdown都不一定把所有子区间都更新，因此会有更下面的区间没更新，而且**既然是区间操作的pushdown一定是有lazy tag的**，这个lazy tag就是xor次数，即**lazy tag一定和操作性质有关，且维护的是序列中每一个数的信息**每次修改^1就好了

Code：

#include <bits/stdc++.h>
    #define int long long
    const int mxn=2e5+10;
    const int mxe=2e5+10;
    const int Inf=-0x3f3f3f3f;
    using namespace std;
    struct Tree{
        int val,lazy;
    }tree[mxe<<2];
    
    string s;
    int n,m,op,l,r;
    int a[mxn];
    void pushup(int rt){
        tree[rt].val=tree[rt<<1].val+tree[rt<<1|1].val;
    }
    void pushdown(int rt,int tot){
        if(tree[rt].lazy){
            tree[rt<<1].lazy^=1;
            tree[rt<<1|1].lazy^=1;
            tree[rt<<1].val=(tot-tot/2)-tree[rt<<1].val;
            tree[rt<<1|1].val=(tot/2)-tree[rt<<1|1].val;
            tree[rt].lazy=0;
        }
    }
    int query(int rt,int l,int r,int x,int y,Tree *tree){
        if(x<=l&&r<=y){
            return tree[rt].val;
        }
        if(tree[rt].lazy!=0) pushdown(rt,r-l+1);
        int mid=l+r>>1;
        int res=0;
        if(x<=mid) res+=query(rt<<1,l,mid,x,y,tree);
        if(y>mid) res+=query(rt<<1|1,mid+1,r,x,y,tree);
        return res;
    }
    void modify(int rt,int l,int r,int x,int y,Tree *tree){
        if(x<=l&&r<=y){
            tree[rt].lazy^=1;
            tree[rt].val=(r-l+1)-tree[rt].val;
            return;
        }
        if(tree[rt].lazy!=0) pushdown(rt,r-l+1);
        int mid=l+r>>1;
        if(x<=mid) modify(rt<<1,l,mid,x,y,tree);
        if(y>mid) modify(rt<<1|1,mid+1,r,x,y,tree);
        pushup(rt);
    }
    void build(int rt,int l,int r,Tree *tree){
        tree[rt].lazy=0;
        if(l==r){
            tree[rt].val=a[l];
            return;
        }
        int mid=l+r>>1;
        build(rt<<1,l,mid,tree);
        build(rt<<1|1,mid+1,r,tree);
        pushup(rt);
    }
    void solve(){
        cin>>n>>m;
        cin>>s;
        s=" "+s;
        for(int i=1;i<=n;i++) a[i]=s[i]-'0';
        build(1,1,n,tree);
        for(int i=1;i<=m;i++){
            cin>>op>>l>>r;
            if(op==0){
                modify(1,1,n,l,r,tree);
            }else{
                cout<<query(1,1,n,l,r,tree)<<'\n';
            }
        }
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

[P2574 XOR_ - _ _ _ _luogu.com.cn]: https://www.luogu.com.cn/problem/P2574
[e3255225ca917fa18b225a6c919fb53e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/4ffb42f7c4574584ac8a00786fcd004d.png