这个题意翻译起来有点猥琐啊,还是和谐一点吧

和涂颜色差不多,区间初始都为1,然后操作都是将x到y改为z,注意 是改为z,不是加或减,最后输出区间总值

也是线段树加lazy操作

1 #include
     
       2 using namespace std; 3 struct point { 4     int l,r; 5     int val,sum; 6 }; 7 point tree[400007]; 8 void build(int i,int left,int right) 9 {10     tree[i].l=left,tree[i].r=right;11     tree[i].val=0;12     if (left==right) {tree[i].sum=1;return;}13     int mid=(left+right)/2;14     build(i*2,left,mid);15     build(i*2+1,mid+1,right);16     tree[i].sum=tree[i*2].sum+tree[i*2+1].sum;17 }18 int update(int i,int left,int right,int val)19 {20     if (right==tree[i].r&&left==tree[i].l)21     {22         tree[i].val=val;23         return tree[i].sum=(right-left+1)*val;24     }25     if (tree[i].val)26     {27         tree[i*2].val=tree[i*2+1].val=tree[i].val;28         tree[i*2].sum=(tree[i*2].r-tree[i*2].l+1)*tree[i].val;29         tree[i*2+1].sum=(tree[i*2+1].r-tree[i*2+1].l+1)*tree[i].val;30         tree[i].val=0;31     }32     int mid=(tree[i].r+tree[i].l)/2;33     if (left>mid) return tree[i].sum=update(i*2+1,left,right,val)+tree[i*2].sum;34     else if (right<=mid) return tree[i].sum=update(i*2,left,right,val)+tree[i*2+1].sum;35     else  return tree[i].sum=update(i*2+1,mid+1,right,val)+update(i*2,left,mid,val);36 }37 int main()38 {39     int t,n,m,x,y,z,sum;40     while (~scanf("%d",&t))41     {42         sum=1;43         while (t--)44         {45             scanf("%d %d",&n,&m);46             build(1,1,n);47             while (m--)48             {49                 scanf("%d %d %d",&x,&y,&z);50                 update(1,x,y,z);51             }52             printf("Case %d: The total value of the hook is %d.\n",sum++,tree[1].sum);53         }54     }55     return 0;56 }
     

 

 

这个和上面一样,只是变成了加上z,所以就变成了在原有的值上再加,+=，改改就行,数值比较大,应该用int64

 

1 #include
     
       2 #define ll __int64 3 using namespace std; 4 struct point { 5     ll l,r; 6     ll val,sum; 7 }; 8 point tree[400007]; 9 ll num[100007];10 void build(ll i,ll left,ll right)11 {12     tree[i].l=left,tree[i].r=right;13     tree[i].val=0;14     if (left==right) {tree[i].sum=num[left];return;}15     int mid=(left+right)/2;16     build(i*2,left,mid);17     build(i*2+1,mid+1,right);18     tree[i].sum=tree[i*2].sum+tree[i*2+1].sum;19 }20 ll update(ll i,ll left,ll right,ll val)21 {22     if (right==tree[i].r&&left==tree[i].l)23     {24         tree[i].val+=val;25         return tree[i].sum+=(right-left+1)*val;26     }27     if (tree[i].val)28     {29         tree[i*2].val+=tree[i].val;30         tree[i*2+1].val+=tree[i].val;31         tree[i*2].sum+=(tree[i*2].r-tree[i*2].l+1)*tree[i].val;32         tree[i*2+1].sum+=(tree[i*2+1].r-tree[i*2+1].l+1)*tree[i].val;33         tree[i].val=0;34     }35     int mid=(tree[i].r+tree[i].l)/2;36     if (left>mid) return tree[i].sum=update(i*2+1,left,right,val)+tree[i*2].sum;37     else if (right<=mid) return tree[i].sum=update(i*2,left,right,val)+tree[i*2+1].sum;38     else  return tree[i].sum=update(i*2+1,mid+1,right,val)+update(i*2,left,mid,val);39 }40 ll find(ll i,ll left,ll right)41 {42     if (left>tree[i].r&&right
      
       mid) return find(i*2+1,left,right);54     else if (right<=mid) return find(i*2,left,right);55     else return find(i*2,left,mid)+find(i*2+1,mid+1,right);56 }57 int main()58 {59     ll n,m,i,z,x,y;60     char op;61     while (~scanf("%I64d %I64d",&n,&m))62     {63        for (i=1;i<=n;i++)64           scanf("%I64d",&num[i]);65        build(1,1,n);66        while (m--)67        {68            scanf(" %c",&op);69            if (op=='C')70            {71                scanf("%I64d %I64d %I64d",&x,&y,&z);72                update(1,x,y,z);73            }74            else75            {76                scanf("%I64d %I64d",&x,&y);77                printf("%I64d\n",find(1,x,y));78            }79        }80     }81     return 0;82 }