2022湖北省赛 L 裸线段树

比眉伴天荒 2024-03-25 20:43 38阅读 0赞

**有人不会裸线段树**

有人没有pushdown调了两小时**裸线段树**

早该414了

[L (codeforces.com)][L _codeforces.com]

题意：

给定一段数，操作有区间加和单点锁定某一值，如果某一位置被锁定，那么区间加不包含这个位置，询问为区间和。

思路：

**对于修改查询的DS题，有个普遍的思路是：**

**先去确定一些询问需要维护的东西**

**然后再去看修改操作对询问要维护的东西的贡献**

**即：特殊的修改操作等效成询问维护的操作形式**

**线段树题的步骤：**

1.  **先去确定好要维护几个序列（不同序列对应不同的线段树数组）**

1.  **再去确定对于一个序列需要维护的性质（一个性质对应一个tag）**

1.  **在pushdown的时候考虑操作对tag的贡献**

1.  **在pushup的时候考虑怎么从两个子区间得到大区间**

对于这道题，有四种操作：

![0524c92c2f68d2c6767114db69630e9e.png][]

询问只有一种，询问区间和

然后去看修改：每次修改都是把所有s=1的值区间加x

那么这种操作对区间和的贡献就是这个区间的s=1的个数\*x

因此可以得出我们还需要维护区间s=1的个数

然后再去想，修改操作对区间cnt的影响

只有1和2操作会对cnt有影响

然后就可以开始写了，我们只需维护区间和和区间s=1的cnt就行了

然后就是pushdown操作

**在pushdown操作的时候，往左区间和右区间分别加上对应比例的贡献**

![220100a94c7a3944ff8621bbecd7d9dd.png][]

Code：

#include <bits/stdc++.h>
    using namespace std;
    #define int long long
    using i64 = long long;
    const int mxn=1e6+10;
    const int mxe=1e6+10;
    struct ty{
        int sum,cnt,lazy;
    }tree[mxe<<2];
    int n,Q,op,x,l,r;
    int a[mxn],s[mxn];
    void pushup(int rt){
        tree[rt].sum=tree[rt<<1].sum+tree[rt<<1|1].sum;
        tree[rt].cnt=tree[rt<<1].cnt+tree[rt<<1|1].cnt;
    }
    void pushdown(int rt){
        tree[rt<<1].lazy+=tree[rt].lazy;
        tree[rt<<1|1].lazy+=tree[rt].lazy;
        tree[rt<<1].sum+=tree[rt<<1].cnt*tree[rt].lazy;
        tree[rt<<1|1].sum+=tree[rt<<1|1].cnt*tree[rt].lazy;
        tree[rt].lazy=0;
    }
    void build(int rt,int l,int r){
        tree[rt].cnt=r-l+1;
        if(l==r){
            tree[rt].sum=a[l];
            tree[rt].cnt=s[l];
            return;
        }
        int mid=l+r>>1;
        build(rt<<1,l,mid);
        build(rt<<1|1,mid+1,r);
        pushup(rt);
    }
    void modify1(int rt,int l,int r,int x){
        if(s[x]) tree[rt].cnt++;
        else tree[rt].cnt--;
        if(l==r){
            return;
        }
        pushdown(rt);
        int mid=l+r>>1;
        if(x<=mid) modify1(rt<<1,l,mid,x);
        else modify1(rt<<1|1,mid+1,r,x);
        pushup(rt);
    }
    int query1(int rt,int l,int r,int x,int y){
        if(x<=l&&r<=y){
            return tree[rt].cnt;
        }
        int mid=l+r>>1;
        int res=0;
        if(x<=mid) res+=query1(rt<<1,l,mid,x,y);
        if(y>mid) res+=query1(rt<<1|1,mid+1,r,x,y);
        return res;
    }
    void modify2(int rt,int l,int r,int x,int y,int t){
        if(x<=l&&r<=y){
            tree[rt].lazy+=t;
            tree[rt].sum+=tree[rt].cnt*t;
            return;
        }
        if(tree[rt].lazy!=0) pushdown(rt);
        int mid=l+r>>1;
        if(x<=mid) modify2(rt<<1,l,mid,x,y,t);
        if(y>mid) modify2(rt<<1|1,mid+1,r,x,y,t);
        pushup(rt);
    }
    int query2(int rt,int l,int r,int x,int y){
        if(x<=l&&r<=y){
            return tree[rt].sum;
        }
        if(tree[rt].lazy!=0) pushdown(rt);
        int mid=l+r>>1;
        int res=0;
        if(x<=mid) res+=query2(rt<<1,l,mid,x,y);
        if(y>mid) res+=query2(rt<<1|1,mid+1,r,x,y);
        return res;
    }
    void solve(){
        cin>>n>>Q;
        for(int i=1;i<=n;i++) cin>>a[i];
        for(int i=1;i<=n;i++) cin>>s[i];
        build(1,1,n);
        while(Q--){
            cin>>op;
            if(op==1){
                cin>>x;
                s[x]^=1;
                modify1(1,1,n,x);
            }else if(op==2){
                cin>>x;
                s[x]^=1;
                modify1(1,1,n,x);
            }else if(op==3){
                cin>>l>>r>>x;
                modify2(1,1,n,l,r,x);
            }else{
                cin>>l>>r;
                cout<<query2(1,1,n,l,r)<<'\n';
            }
        }
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

[L _codeforces.com]: https://codeforces.com/gym/103729/problem/L
[0524c92c2f68d2c6767114db69630e9e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/cb08d5ac06694247b846cedce83cc0f8.png
[220100a94c7a3944ff8621bbecd7d9dd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/ebed307afb4246c7970ee760799d803e.png