真的牛逼，4倍经验

野性酷女 2023-06-04 07:59 50阅读 0赞

**线段树区间异或，四倍经验，666。**

**关于线段树区间异或:**

**就是维护区间0的个数，1的个数，取反实际上就是把他们swap一下，总数不变，lazy标记改为^1即可**

**洛谷有四倍经验**  **给出题号：P2574，SP7259，P2846，P3870。**

**[P3870][]代码如下：**

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<bits/stdc++.h>
    using namespace std;
    const int maxn=1e6+7;
    int n,m; 
    struct node{
        int l,r,sum1,sum0,lazy;
    }tree[maxn*4];
    void build(int now,int l,int r){
        tree[now].l=l,tree[now].r=r,tree[now].lazy=0;
        if(l==r){
            tree[now].sum0=1;
             return;    
        }
        int mid=(tree[now].l+tree[now].r)>>1;
        build(now<<1,l,mid);
        build(now<<1|1,mid+1,r);
        tree[now].sum0=tree[now<<1].sum0+tree[now<<1|1].sum0;
    }
    void pushdown(int now){
        if(tree[now].lazy){
            swap(tree[now<<1].sum0,tree[now<<1].sum1);
            swap(tree[now<<1|1].sum0,tree[now<<1|1].sum1);
            tree[now<<1].lazy^=1;
            tree[now<<1|1].lazy^=1;
            tree[now].lazy=0;
        }
    }
    void update(int now,int l,int r){
        if(tree[now].l>=l&&tree[now].r<=r){
            swap(tree[now].sum0,tree[now].sum1);
            tree[now].lazy^=1;
            return;
        }
        pushdown(now);
        int mid=(tree[now].l+tree[now].r)>>1;
        if(l<=mid) update(now<<1,l,r);
        if(r>mid) update(now<<1|1,l,r);
        tree[now].sum0=tree[now<<1].sum0+tree[now<<1|1].sum0;
        tree[now].sum1=tree[now<<1].sum1+tree[now<<1|1].sum1;
    }
    int query(int now,int l,int r){
        if(tree[now].l>=l&&tree[now].r<=r) return tree[now].sum1;
        pushdown(now);
        int val=0;
        int mid=(tree[now].l+tree[now].r)>>1;
        if(l<=mid) val+=query(now<<1,l,r);
        if(r>mid) val+=query(now<<1|1,l,r);
        return val;
    }
    int main(){
        scanf("%d%d",&n,&m);
        int opt,l,r;
        build(1,1,n);
        for(int i=1;i<=m;i++){    
            scanf("%d%d%d",&opt,&l,&r);
            if(opt==0) update(1,l,r);
            else printf("%d\n",query(1,l,r));
        }
        return 0;
    }

**其他的直接CV就行了**

转载于:https://www.cnblogs.com/LJB666/p/11322615.html

[P3870]: https://www.luogu.org/problem/P3870
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230601/e2ba8ab5891a4e35a1a828ad34acec9b.png