Contents

1. 1. hdu 1698：
2. 2. 题目：
3. 3. 分析：

hdu 1698：

题目：

现在屠夫愿意做勾上一些操作。

让我们从1到N的钩对每一个操作的连续金属棍棒，屠夫可以改变连续金属棍棒，编号从X到Y，进铜枝，枝银或金棒。
钩的总价值计算为N金属棍棒值的总和。更精确地说，对于每一种粘的值的计算方法如下：

对于每一个铜棒，该值为1。
对于每个银棒，该值为2。
对于每一个金杖，这个值是3。

屠夫想要执行操作之后知道钩的总价值。
您可以考虑原来的钩是由铜枝。

输入由多个测试用例。输入的第一行是的情况下的数量。有没有10多例。
对于每一种情况下，第一行包含一个整数N，1 <= N <= 100,000，这是屠夫的肉钩和第二线的支数包含一个整数Q，0 <= Q <= 100,000，这是的操作的数量。
下一个Q行，每行有三个整数，X，Y，1 <= X <= Y <= N，Z，1 <= Z <= 3，它定义一个操作：改变根据X编号Y的枝到金属那种Z，其中Z = 1表示铜样，Z = 2表示银种类和Z = 3代表的黄金kind.ticks。更精确地说，对于每一种粘的值的计算方法如下：

对于每一个铜棒，该值为1。
对于每个银棒，该值为2。
对于每一个金杖，这个值是3。

屠夫想要执行操作之后知道钩的总价值。
您可以考虑原来的钩是由铜枝。

分析：

1 成段更新和单点更新是不同的，单点更新是要更新到叶子节点，但是对于成段更新是
更新到某个区间即可，找个区间是当前需要的更新的区间的最大的子区间

2 成段更新需要维护一个“延时标记”，初始化看情况。我们先把标记放在一个大的区
间，下次遇到的时候再进行向下的更新(标记传递)

3 建好线段树然后更新，最后输出节点1的和即可

//这道题可以和hdu1556对比下，1556主要是区间内积累，而这道题是区间内改变
//所以有很多地方的+= 改为了 =

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define Mid(x,y) ((x + y) >> 1)
#define Lson(x) (x << 1)
#define Rson(x) (x << 1 | 1)
#define MAXN 100010

struct Node{
    int left;
    int right;
    int mark;//延时标记
    int sum;
}node[MAXN << 2];

void push_up(int pos){

    node[pos].sum = node[Lson(pos)].sum + node[Rson(pos)].sum;
}

void push_down(int pos){

    if(node[pos].mark){
        node[Lson(pos)].mark = node[pos].mark;
        node[Rson(pos)].mark = node[pos].mark;
        //这里是将小钩子改变为其他的种类,所以不是一个积累的过程而是改变
        node[Lson(pos)].sum = node[Lson(pos)].mark * (node[Lson(pos)].right - node[Lson(pos)].left + 1);
        node[Rson(pos)].sum = node[Rson(pos)].mark * (node[Rson(pos)].right - node[Rson(pos)].left + 1);
        node[pos].mark = 0;
    }
}

void build_tree(int left, int right, int pos){

    node[pos].left = left;
    node[pos].right = right;
    node[pos].mark = 1;//所有的钩子一开始都初始化为铜钩子属性
    if(left == right){
        node[pos].sum = 0;
        return ;
    }
    int mid = Mid(left, right);
    build_tree(left, mid, Lson(pos));
    build_tree(mid + 1, right, Rson(pos));
    push_up(pos);
}

void update(int left, int right, int value, int pos){

    if(left <= node[pos].left && node[pos].right <= right){
        node[pos].mark = value;//改变区间范围内钩子的属性
        node[pos].sum = value * (node[pos].right - node[pos].left + 1);//改变区间范围内钩子的总价值
        return ;
    }
    push_down(pos);
    int mid = Mid(node[pos].left, node[pos].right);
    if(right <= mid)
        update(left, right, value, Lson(pos));
    else if(left > mid)
        update(left, right, value, Rson(pos));
    else{
        update(left, mid, value, Lson(pos));
        update(mid + 1, right, value, Rson(pos));
    }
    push_up(pos);
}

int main(){

    int T, n, q, x, y, value, Case = 1;
    scanf("%d", &T);
    while(T--){
        scanf("%d%d", &n, &q);
        build_tree(1, n, 1);
        while(q--){
            scanf("%d%d%d", &x, &y, &value);
            update(x, y, value, 1);
        }
        printf("Case %d: The total value of the hook is %d.\n" , Case++ , node[1].sum);
    }
    return 0;
}