hdu:张煊的金箍棒（3）（线段树）

Problem Description
张煊的金箍棒升级了！

升级后的金箍棒是由N段相同长度的金属棒连接而成（最开始每段金属棒的价值都是1，从1到N编号）；

张煊作为金箍棒的主人，可以对金箍棒任意一段施展魔法操作，每次操作就是将一段连续的金属棒（从X到Y编号）每一段都增加价值Z（Z为1,2,3三种）。

现在，张煊想知道执行M次操作后某一段金箍棒总值。

有Q次查询，每次询问一段（A到B）金箍棒的价值和。

Input
输入的第一行是测试数据的组数（不超过10个）。

对于每组测试数据，第一行包含一个整数N（1 <= N <= 100000），表示金箍棒有N节组成，第二行包含两个整数M（0 <= M <= 100,000）和 Q（1 <= Q <= 100），分别表示执行M次魔法操作，有Q次查询。

接下来的M行，每行包含三个整数X，Y，Z（1 <= X <= Y <= N，1 <= Z <= 3），它定义了一个操作：将从X到Y编号的金属棒每一段的价值增加Z，其中 Z = 1或者 Z = 2 或者 Z = 3。

接下来的Q行，每行包含二个整数A和B（1 <= A <= B <= N），表示查询从A到B这一段金箍棒的价值总和。

Output
对于每组测试数据，请输出Q行，每行一个数字，表示一次查询的结果。

输入样例

1
10
2 2
1 5 2
5 9 3
1 4
3 6
 

输出样例

12
16

基础的线段树应用，注意各个函数的用处和二分的写法
附ac代码

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
struct tr {
    LL val;
    LL lazy;
}t[4 * N];
void Pushup(int rt)
{
    t[rt].val = t[rt << 1].val + t[rt << 1 | 1].val;
}
void Pushdown(int rt, int ll, int rl)
{
    if (t[rt].lazy)
    {
        t[rt << 1].val += t[rt].lazy * ll;
        t[rt << 1 | 1].val += t[rt].lazy * rl;
        //注意lazy是+=
        t[rt << 1].lazy += t[rt].lazy;
        t[rt << 1 | 1].lazy += t[rt].lazy;
        t[rt].lazy = 0;
    }
}
void Build(int l, int r, int rt)
{
    if (l == r)
    {
        t[rt].val = 1;
        return;
    }
    int m = (l + r) >> 1;
    Build(l, m, rt << 1);
    Build(m + 1, r, rt << 1 | 1);
    Pushup(rt);
    //Pushup()的意义：建立好左右子树后合并到根节点
}
void Update(int L, int R, int c, int l, int r, int rt)
{
    if (L <= l && R >= r)
    {
        t[rt].val += (r - l + 1) * c;
        t[rt].lazy += c;
        return;
    }
    int m = (l + r) >> 1;
    Pushdown(rt, m - l + 1, r - m);
    //每次更新前将rt点下推至左右子节点
    if (L <= m) Update(L, R, c, l, m, rt << 1);
    if (R > m) Update(L, R, c, m + 1, r, rt << 1 | 1);
    Pushup(rt);
    //更新完左右子树再更新根节点
}
LL Query(int L, int R, int l, int r, int rt)
{
    if (r<L || l>R) return 0;
    if (L <= l && R >= r) return t[rt].val;
    int m = (l + r) >> 1;
    Pushdown(rt, m - l + 1, r - m);
    //每次查询子树前下推一次
    return Query(L, R, l, m, rt<<1) + Query(L, R, m + 1, r, rt<<1|1);
}
int main()
{
    int p, n, m, q;
    int x, y, z;
    scanf("%d", &p);
    while (p--)
    {
        scanf("%d%d%d", &n, &m, &q);
        memset(t, 0, sizeof(t));//清空t数组
        Build(1, n, 1);
        while (m--)
        {
            scanf("%d%d%d", &x, &y, &z);
            Update(x, y, z, 1, n, 1);
        }
        while (q--)
        {
            scanf("%d%d", &x, &y);
            printf("%lld\n", Query(x, y, 1, n, 1));
        }
    }
    return 0;
}