Zcube世界

题意：初始一序列为1，各种操作后序列总和多少？

分析：各种操作->线段树，本以为很水，用之前自己写的线段树，各种超时+郁闷，后来找到自己第一次接触线段树的那道题，标程里面用到了线段树遗传效应，省了不少时间；

代码：

#include <cstdio>
#include <cstring>

const int M = 100005;

int vv;

struct node {
    int a, b, m, r; //用r 做遗传
}tree[4*M];

void build(int x, int y, int k) {
    tree[k].a = x;
    tree[k].b = y;
    tree[k].r = 0;
    if (y > x) {
        int mid = (x+y) >> 1;
        build(x, mid, k<<1);
        build(mid+1, y, k<<1|1);
        tree[k].m = tree[k<<1].m + tree[k<<1|1].m;
    }
    else if (x == y) {
        tree[k].m = 1;
    }
}
void operate(int x, int y, int k) {
    int mid = (tree[k].a+tree[k].b)>>1;
    if (x==tree[k].a && tree[k].b==y) { //不需要更新到每个结点
        tree[k].m = vv * (y - x +1);
        tree[k].r = vv; //用r 先记录此次操作
        return;
    }
    if (tree[k].r!=0) { //如果要对k 的孩子进行操作，则将先前k 的属性r 遗传给左右孩子
        tree[k<<1].m = tree[k].r * (tree[k<<1].b-tree[k<<1].a+1);
        tree[k<<1|1].m = tree[k].r * (tree[k<<1|1].b-tree[k<<1|1].a+1);
        tree[k<<1].r = tree[k<<1|1].r = tree[k].r;
        tree[k].r = 0; //遗传后清零
    }
    if (x > mid) {
        operate(x, y, k<<1|1);
    }
    else if (y <= mid) {
        operate(x, y, k<<1);
    }
    else {
        operate(x, mid, k<<1);
        operate(mid+1, y, k<<1|1);
    }
    tree[k].m = tree[k<<1].m + tree[k<<1|1].m;
}

int main() {
    int tc, cc = 1;
    int n, q;
    scanf("%d", &tc);
    while (tc--) {
        scanf("%d", &n);
        build(1, n, 1);
        scanf("%d", &q);
        while (q--) {
            int x, y;
            scanf("%d%d%d", &x, &y, &vv);
            operate(x, y, 1);
        }

        printf("Case %d: The total value of the hook is %d.\n", cc++, tree[1].m); 
    }
    return 0;
}