Just a Hook HDU

In the game of DotA, Pudge’s meat hook is actually the most horrible thing for most of the heroes. The hook is made up of several consecutive metallic sticks which are of the same length. 



Now Pudge wants to do some operations on the hook. 

Let us number the consecutive metallic sticks of the hook from 1 to N. For each operation, Pudge can change the consecutive metallic sticks, numbered from X to Y, into cupreous sticks, silver sticks or golden sticks. 
The total value of the hook is calculated as the sum of values of N metallic sticks. More precisely, the value for each kind of stick is calculated as follows: 

For each cupreous stick, the value is 1. 
For each silver stick, the value is 2. 
For each golden stick, the value is 3. 

Pudge wants to know the total value of the hook after performing the operations. 
You may consider the original hook is made up of cupreous sticks. 

InputThe input consists of several test cases. The first line of the input is the number of the cases. There are no more than 10 cases. 
For each case, the first line contains an integer N, 1<=N<=100,000, which is the number of the sticks of Pudge’s meat hook and the second line contains an integer Q, 0<=Q<=100,000, which is the number of the operations. 
Next Q lines, each line contains three integers X, Y, 1<=X<=Y<=N, Z, 1<=Z<=3, which defines an operation: change the sticks numbered from X to Y into the metal kind Z, where Z=1 represents the cupreous kind, Z=2 represents the silver kind and Z=3 represents the golden kind. 
OutputFor each case, print a number in a line representing the total value of the hook after the operations. Use the format in the example. 
Sample Input

1
10
2
1 5 2
5 9 3

Sample Output

Case 1: The total value of the hook is 24.

题意：有一个多截棍，起初它是有同制造的，现在我想把指定区间内的棍都换成其他材质的，比如银的，或金的。一节铜双截棍是1元，一节银双截棍是2元，一节金双截棍是3元。问最后这个多截棍值多少钱。
输入第一行表示样例数(小于10)，然后每个样例的第一行为多截棍的节数（1~100000），第二行为改变的次数q(1~100000),然后q行，每行三个数a,b,c：表示将a到b的棍换成价值为c元棍。
输入格式按照样例。

思路：这是一个简单的线段树题，它只用到了区间修改的方法，我就不多说了。

代码：

#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#include <sstream>
#include <iostream>
#define mod 998244353
#define eps 1e-6
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;

struct node
{
    //l表示左边，r表示右边，sum表示该线段的值
    int l,r,sum;
    //lazy为标记，为方便区间修改
    int lazy;
};
node no[100000*8];

//初始化
//k表示当前节点的编号，l表示当前区间的左边界，r表示当前区间的右边界
void build(int k,int l,int r)
{
    no[k].l=l;
    no[k].r=r;
    //如果递归到最低点
    if(l==r)
    {
        no[k].sum=1;
        return ;
    }
    //对半分
    int mid=(l+r)/2;
    //递归到左线段
    build(k*2,l,mid);
    //递归到右线段
    build(k*2+1,mid+1,r);
    //更新当前节点的值
    no[k].sum=no[k*2].sum+no[k*2+1].sum;
}

//传递标记
void pushdown(int k)
{
    //当前节点不是最低层时
    if(no[k].l!=no[k].r)
    {
        //更新子节点的值
        no[k*2].sum=(no[k*2].r-no[k*2].l+1)*no[k].lazy;
        no[k*2+1].sum=(no[k*2+1].r-no[k*2+1].l+1)*no[k].lazy;
        //更新子节点的标记
        no[k*2].lazy=no[k*2+1].lazy=no[k].lazy;
    }
    //清除当前节点的标记
    no[k].lazy=0;
}

//区间修改
void change(int k,int l,int r,int x)
{
    //检查并下传标记
    if(no[k].lazy)
    {
        pushdown(k);
    }
    //到对应层时更新值与标记
    if(no[k].l==l&&no[k].r==r)
    {
        no[k].sum=(no[k].r-no[k].l+1)*x;
        no[k].lazy=x;
        return ;
    }
    //取中值
    int mid=(no[k].l+no[k].r)/2;
    
    if(r<=mid)
    {
        //如果被修改区间完全在左区间
        change(k*2,l,r,x);
    }
    else if(l>mid)
    {
        //如果被修改区间完全在右区间
        change(k*2+1,l,r,x);
    }
    else
    {
        //如果都不在，就要把修改区间分解成两块，分别往左右区间递归
        change(k*2,l,mid,x);
        change(k*2+1,mid+1,r,x);
    }
    //更新当前节点的值
    no[k].sum=no[k*2].sum+no[k*2+1].sum;
}

int main()
{
    int m,n;
    int ans=1;
    scanf("%d",&m);
    while(m--)
    {
        //对每个测试样例都要初始化
        memset(no,0,sizeof(no));
        scanf("%d",&n);
        //构建线段树
        build(1,1,n);
        int q;
        scanf("%d",&q);
        int a,b,c;
        for(int i=0;i<q;i++)
        {
            scanf("%d %d %d",&a,&b,&c);
            //执行修改操作
            change(1,a,b,c);
        }
        printf("Case %d: The total value of the hook is %d.
",ans++,no[1].sum);
    }
}