hihocoder 1078# 线段树的区间修改模版

我就是我 2022-08-04 08:39 128阅读 0赞

#include<bitset>
    #include<map>
    #include<vector>
    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<cmath>
    #include<stack>
    #include<queue>
    #include<set>
    #define inf 0x3f3f3f3f
    #define mem(a,x) memset(a,x,sizeof(a))
    
    using namespace std;
    
    typedef long long ll;
    typedef pair<int,int> pii;
    
    inline int in()
    {
        int res=0;
        char c;
        while((c=getchar())<'0' || c>'9');
        while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
        return res;
    }
    
    struct st
    {
        int l,r;
        int sum;
        int lazy;
    }a[400040];
    
    inline void PushUp(int i)
    {
        a[i].sum=a[i<<1].sum+a[i<<1|1].sum;
    }
    
    inline void PushDown(int i)
    {
        //if(a[i].lazy && a[i].l==a[i].r)  a[i].sum=a[i].lazy,a[i].lazy=0;
        if(a[i].lazy)
        {
            a[i<<1].lazy=a[i<<1|1].lazy=a[i].lazy;
            a[i<<1].sum=(a[i<<1].r-a[i<<1].l+1)*a[i].lazy;
            a[i<<1|1].sum=(a[i<<1|1].r-a[i<<1|1].l+1)*a[i].lazy;
            a[i].lazy=0;
        }
    }
    
    void Build(int l,int r,int i)
    {
        a[i].l=l,a[i].r=r;
        a[i].lazy=0;
        if(l==r)
        {
            a[i].sum=in();
    
            return;
        }
        int mid=(l+r)>>1;
        Build(l,mid,i<<1);
        Build(mid+1,r,i<<1|1);
        PushUp(i);
    }
    
    void Update(int l,int r,int val,int i)
    {
        if(a[i].l>=l && a[i].r<=r)
        {
            a[i].lazy=val;
            a[i].sum=(r-l+1)*val;
            return;
        }
        PushDown(i);
        int mid=(a[i].l+a[i].r)>>1;
        if(mid>=r)Update(l,r,val,i<<1);
        else if(l>mid)Update(l,r,val,i<<1|1);
        else
        {
            Update(l,mid,val,i<<1);
            Update(mid+1,r,val,i<<1|1);
        }
        PushUp(i);
    }
    int Query(int l,int r,int i)
    {
        if(a[i].l>=l && a[i].r<=r)return a[i].sum;
        if(a[i].l>r || a[i].r<l)return 0;
        PushDown(i);          //别漏了
        return Query(l,r,i<<1)+Query(l,r,i<<1|1);
    }
    int main()
    {
    
        int n=in();
        Build(1,n,1);
        int m=in();
        for(int i=0;i<m;i++)
        {
            int flag=in();
    
            if(flag==0)
            {
                int t1=in(),t2=in();
                printf("%d\n",Query(t1,t2,1));
            }
            else
            {
                int t1=in(),t2=in(),val=in();
                Update(t1,t2,val,1);
            }
        }
        return 0;
    }