Just a Hook （线段树）

Just a Hook

Within the context of Dota 2, Pudge's meat hook stands out as a weapon that consistently poses a significant threat to opponents. The construct consists of multiple consecutive metal rods, all precisely equal in length.

Now Pudge wants to do some operations on the hook.

Let us label the consecutive metallic sticks on the hook from 1 to N. For each operation performed by Pudge, he can transform a range of consecutive metallic sticks—those numbered from X to Y—into either cupreous, silver, or golden sticks. The total value of this hook is determined by summing up its component values for all N metallic sticks. More precisely, each type of stick contributes its own value based on specific mathematical formulas.

For every copper stick, its value amounts to one.
Each silver rod holds a value of two.
Every gold bar has a valuation of three.

Pudge is interested in determining the total value of the hook after these operations have been executed. It can be assumed that the original hook is constructed from copper sticks, which are likely composed of multiple components that contribute individually to its overall value.

Input

The input comprises several test cases. The first line of each test case represents its count. Each case begins with two lines: one for N (sticks' count) and another for Q (number of operations). Following this are Q lines detailing each operation. Each operation consists of three integers X (start index), Y (end index), and Z (metal type). Specifically: X must be between 1 and Y; Y cannot exceed N; Z can be cupreous (Z=1), silver (Z=2), or golden (Z=3).

Output

For each test scenario, output a numerical value per case showing the total hook value following all operations. Adhere to formatting guidelines as demonstrated.

Sample Input

Sample Output

题目大意：

长度为n的一系列棍棒，在完成m次操作后需将编号为a到b的所有棍棒更换为c材质，并计算整体价值；其中铜、银、金对应的价值分别为1、2、3单位；同时采用线段树进行区间更新操作

代码：

 #include<stdio.h>

    
 #include<string.h>
    
 #include<algorithm>
    
 using namespace std;
    
 #define N 100005
    
 #define lson l,m,rt<<1
    
 #define rson m+1,r,rt<<1|1
    
 int sum[N<<2],lazy[N<<2];
    
 void pushup(int rt)
    
 {
    
     sum[rt]=sum[rt<<1]+sum[rt<<1|1];
    
 }
    
 void pushdown(int rt,int m)
    
 {
    
     if(lazy[rt])
    
     {
    
     lazy[rt<<1]=lazy[rt];
    
     lazy[rt<<1|1]=lazy[rt];
    
     sum[rt<<1]=lazy[rt]*(m-(m>>1));
    
     sum[rt<<1|1]=lazy[rt]*(m>>1);
    
     lazy[rt]=0;
    
     }
    
 }
    
 void built(int l,int r,int rt)
    
 {
    
     lazy[rt]=0;
    
     if(l==r){sum[rt]=1;return ; }
    
     int m=(l+r)>>1;
    
     built(lson);
    
     built(rson);
    
     pushup(rt);
    
 }
    
 void updata(int L,int R,int c,int l,int r,int rt)
    
 {
    
     if(L<=l&&r<=R)
    
     {
    
     lazy[rt]=c;
    
     sum[rt]=(int)c*(r-l+1);
    
     return ;
    
     }
    
     pushdown(rt,r-l+1);
    
     int m=(l+r)>>1;
    
     if(L<=m) updata(L,R,c,lson);
    
     if(m<R) updata(L,R,c,rson);
    
     pushup(rt);
    
 }
    
 int main()
    
 {
    
     int t,k=1;
    
     scanf("%d",&t);
    
     while(t--)
    
     {
    
     int n,m;
    
     scanf("%d%d",&n,&m);
    
     built(1,n,1);
    
     while(m--)
    
     {
    
         int a,b,c;
    
         scanf("%d%d%d",&a,&b,&c);
    
         updata(a,b,c,1,n,1);
    
     }
    
     printf("Case %d: The total value of the hook is %d.\n",k++,sum[1]);
    
     }
    
     return 0;
    
 }
    
    
    
    
    AI写代码