hdu 1698 线段树的区间修改模板~~

Love The Way You Lie 2022-08-02 15:41 211阅读 0赞

把给定区间内的数全部更改为另一个数，线段树区间更新 模版，参考别人的代码

#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,sum;
        int lazy,tag;
    }a[100010<<2]; //记得开4倍，老忘记
    
    void build(int l,int r,int i)//递归的建树就行
    {
        a[i].l=l;
        a[i].r=r;
        a[i].tag=0;
        a[i].lazy=0;
        if(l==r)
        {
            a[i].sum=1;
            return;
        }
        int mid=(l+r)>>1;
        build(l,mid,i<<1);
        build(mid+1,r,i<<1|1);
        a[i].sum=a[i<<1].sum+a[i<<1|1].sum;
    }
    
    void update(int l,int r,int x,int i)
    {
        if(a[i].l==l && a[i].r==r) //成端更新
        {
            a[i].lazy=1;
            a[i].tag=x;
            a[i].sum=(r-l+1)*x;    
            return;
        }
        int mid=(a[i].l+a[i].r)>>1;
        if(a[i].lazy==1)    //当前节点有lazy标记
        {
            a[i].lazy=0;
            update(a[i].l,mid,a[i].tag,i<<1);  //向下更新左半边，传参数应该传tag
            update(mid+1,a[i].r,a[i].tag,i<<1|1);//向下更新右半边
            a[i].tag=0;                         //设为零
        }
        if(r<=mid)update(l,r,x,i<<1);      //要更新的区间在当前区间的左边
        else if(l>mid)update(l,r,x,i<<1|1);//在右边
        else                                  //两边都在
        {
            update(l,mid,x,i<<1);           //传mid
            update(mid+1,r,x,i<<1|1);
        }
        a[i].sum=a[i<<1].sum+a[i<<1|1].sum; //更新
    }
    
    int main()
    {
        int T=in();
        int iCase=1;
        while(T--)
        {
            int n=in();
            build(1,n,1);
            int m=in();
            int x,y,z;
            while(m--)
            {
                x=in(),y=in(),z=in();
                update(x,y,z,1);
            }
            printf("Case %d: The total value of the hook is %d.\n",iCase++,a[1].sum);
        }
        return 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 lazy,sum;
    }a[400020];
    
    
    void PushUp(int i)
    {
        a[i].sum=a[i<<1].sum+a[i<<1|1].sum;
    }
    
    void PushDown(int i)
    {
        if(a[i].lazy)
        {
            a[i<<1].lazy=a[i].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=1;
            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(mid<l)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 main()
    {
        int T=in();
        for(int ii=1;ii<=T;ii++)
        {
            int n=in();
            build(1,n,1);
            int m=in();
            while(m--)
            {
                int t1=in(),t2=in(),t3=in();
                update(t1,t2,t3,1);
            }
            printf("Case %d: The total value of the hook is %d.\n",ii,a[1].sum);
        }
        return 0;
    }