【线段树应用】数据结构

蔚落 2024-03-25 21:06 46阅读 0赞

[1008-数据结构\_2021秋季算法入门班第十一章习题：线段树、树状数组 (nowcoder.com)][1008-_2021_ _nowcoder.com]

题意：

![9b7d5ce2b81ba316958bb0426ce5b306.png][]

思路：

**线段树应用的一般思路：**

1.  **先去确定需要维护几个序列（一个序列对应一棵线段树）**

1.  **再去确定对于一个序列需要维护的东西**

1.  **再去考虑计算修改操作对需要维护的答案的贡献需要什么信息，这些信息就是新的需要维护的东西**

1.  **这样对于一个序列所有需要维护的东西就确定了**

1.  **去pushdown里计算修改操作对一棵线段树里的各种tag的贡献，考虑lazy tag的时候考虑要加哪些lazy tag，这个一定是和操作性质有关的，且维护的是序列里每一个数的信息，pushdown的时候注意tag更新顺序**

1.  **去pushup考虑怎么从两个子区间得到一个大区间**

对于这道题：

1.  首先我们需要维护的两个序列，一个是原序列，一个是原序列的平方和

1.  对于这两个序列，我们需要维护的都是区间和

1.  考虑修改操作。这里有三种修改操作：+x，\*x，\*y+x

考虑+x:

对于第一个序列，加上add这个lazy tag就可以了

对于第二个序列，我们这样去计算贡献：

![320f8884cf30db35a9bea556a4a1d8ca.png][]

可以看到我们用tree1的区间和和x和区间长度这些信息就能算出贡献，因此不需要额外加tag

考虑\*x：

对于第一个序列，我们需要加mul这个lazy tag

对于第二个序列，这样去计算贡献：

![244660a7ae02fed8ebab69a0804bf561.png][]

贡献可以直接\*y\*y

还有一种操作:\*y+x：

计算一下贡献就是：

![fd5d755a8230cea4a5250c41b2090c1b.png][]

这样我们一共需要维护哪些tag就确定了

1.  然后就是最重要的一步，在pushdown里根据父结点计算贡献

注意要先算tree2的贡献再算tree1的贡献，因为计算tree2的贡献需要用到旧的tree1，不能先更新tree1再更新tree2

1.  最后pushup就是很简单的左区间+右区间

Code：

#include <bits/stdc++.h>
    #define int long long
    const int mxn=1e5+10;
    const int mxe=2e5+10;
    const int mod=1e9+7;
    const int Mnf=1e18;
    const int Inf=-1e18;
    using namespace std;
    struct Tree{
        int sum,add,mul;
    }tree1[mxe<<2],tree2[mxe<<2];
    
    int n,m,op,l,r,x;
    int a[mxn];
    void pushup(int rt){
        tree1[rt].sum=tree1[rt<<1].sum+tree1[rt<<1|1].sum;
        tree2[rt].sum=tree2[rt<<1].sum+tree2[rt<<1|1].sum;
    }
    void build(int rt,int l,int r){
        tree1[rt].add=tree2[rt].add=0;
        tree2[rt].mul=tree2[rt].mul=1;
        if(l==r){
            tree1[rt].sum=a[l];
            tree2[rt].sum=a[l]*a[l];
            return;
        }
        int mid=l+r>>1;
        build(rt<<1,l,mid);
        build(rt<<1|1,mid+1,r);
        pushup(rt);
    }
    void pushdown(int rt,int tot){
        int x=tree2[rt].add,y=tree2[rt].mul;
    
        //区间乘：
        tree2[rt<<1].add=tree2[rt<<1].add*y+x;
        tree2[rt<<1|1].add=tree2[rt<<1|1].add*y+x;
        tree2[rt<<1].mul*=y;
        tree2[rt<<1|1].mul*=y;
        tree2[rt<<1].sum=tree2[rt<<1].sum*y*y+2*x*y*tree1[rt<<1].sum+x*x*(tot-tot/2);
        tree2[rt<<1|1].sum=tree2[rt<<1|1].sum*y*y+2*x*y*tree1[rt<<1|1].sum+x*x*(tot/2);
    
    
        //区间和：
        tree1[rt<<1].add=tree1[rt<<1].add*y+x;
        tree1[rt<<1|1].add=tree1[rt<<1|1].add*y+x;
        tree1[rt<<1].mul*=y;
        tree1[rt<<1|1].mul*=y;
        tree1[rt<<1].sum=tree1[rt<<1].sum*y+(tot-tot/2)*x;
        tree1[rt<<1|1].sum=tree1[rt<<1|1].sum*y+(tot/2)*x;
    
        tree1[rt].add=tree2[rt].add=0;
        tree1[rt].mul=tree2[rt].mul=1;
    }
    void modify_sum(int rt,int l,int r,int x,int y,int k){
        if(x<=l&&r<=y){
            tree1[rt].add+=k;tree2[rt].add+=k;
            tree2[rt].sum+=2*tree1[rt].sum*k+(r-l+1)*k*k;
            tree1[rt].sum+=k*(r-l+1);
            return;
        }
        if(tree1[rt].add||tree1[rt].mul!=1) pushdown(rt,r-l+1);
        int mid=l+r>>1;
        if(x<=mid) modify_sum(rt<<1,l,mid,x,y,k);
        if(y>mid) modify_sum(rt<<1|1,mid+1,r,x,y,k);
        pushup(rt);
    }
    void modify_mul(int rt,int l,int r,int x,int y,int k){
        if(x<=l&&r<=y){
            tree1[rt].add*=k;tree2[rt].add*=k;
            tree1[rt].mul*=k;tree2[rt].mul*=k;
            tree1[rt].sum*=k;tree2[rt].sum*=k*k;
            return;
        }
        if(tree1[rt].add||tree1[rt].mul!=1) pushdown(rt,r-l+1);
        int mid=l+r>>1;
        if(x<=mid) modify_mul(rt<<1,l,mid,x,y,k);
        if(y>mid) modify_mul(rt<<1|1,mid+1,r,x,y,k);
        pushup(rt);
    }
    int query(int rt,int l,int r,int x,int y,Tree *tree){
        if(x<=l&&r<=y){
            return tree[rt].sum;
        }
        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 solve(){
        cin>>n>>m;
        for(int i=1;i<=n;i++) cin>>a[i];
        build(1,1,n);
        for(int i=1;i<=m;i++){
            cin>>op;
            if(op==1){
                cin>>l>>r;
                cout<<query(1,1,n,l,r,tree1)<<'\n';
            }else if(op==2){
                cin>>l>>r;
                cout<<query(1,1,n,l,r,tree2)<<'\n';
            }else if(op==3){
                cin>>l>>r>>x;
                modify_mul(1,1,n,l,r,x);
            }else{
                cin>>l>>r>>x;
                modify_sum(1,1,n,l,r,x);
            }
        }
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

[1008-_2021_ _nowcoder.com]: https://ac.nowcoder.com/acm/contest/26896/1008
[9b7d5ce2b81ba316958bb0426ce5b306.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/b1058210a82d45ee937b52da5519334c.png
[320f8884cf30db35a9bea556a4a1d8ca.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/de0209d7bf684e65a96cf245f9b7e3eb.png
[244660a7ae02fed8ebab69a0804bf561.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/9bc6520af7ac4b9f9807819ff37d3750.png
[fd5d755a8230cea4a5250c41b2090c1b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/64ee72a480744678b02e4c6bd571bb88.png