题目链接： 传送门
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int N = 500010; int m, p, arr[N]; struct Node { int l, r; int sum, add; } tr[N * 4]; //更新操作 void pushup(int u) { tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum; } //一个标记，暂时把当前结点操作存到该区间的最大根结点中 void pushdown(int u) { Node &root = tr[u], &left = tr[u << 1], &right = tr[u << 1 | 1]; if (root.add) { left.add = root.add, left.sum = (left.r - left.l + 1) * root.add; right.add = root.add, right.sum = (right.r - right.l + 1) * root.add; root.add = 0; } } //创建线段树 void build(int u, int l, int r) { if (l == r) { tr[u] = {l, r, 1, 0}; } else { tr[u].l = l, tr[u].r = r; int mid = l + r >> 1; build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r); pushup(u); } } //查询操作 int query(int u, int l, int r) { if (tr[u].l >= l && tr[u].r <= r) return tr[u].sum; pushdown(u); int mid = tr[u].l + tr[u].r >> 1; int sum = 0; if (l <= mid) sum = query(u << 1, l, r); if (r > mid) sum += query(u << 1 | 1, l, r); return sum; } //修改操作 void modify(int u, int l, int r, int val) { if (tr[u].l >= l && tr[u].r <= r) { tr[u].sum = (tr[u].r - tr[u].l + 1) * val; tr[u].add = val; } else { pushdown(u); int mid = tr[u].l + tr[u].r >> 1; if (l <= mid) modify(u << 1, l, r, val); if (r > mid) modify(u << 1 | 1, l, r, val); pushup(u); } } int main() { int m, n, s, e, t, op, ca = 1; scanf("%d", &t); while(t--) { //多组操作，一定要注意初始化问题 memset(tr, 0, sizeof(tr)); scanf("%d", &n); build(1, 1, n); scanf("%d", &m); while(m--) { scanf("%d%d%d", &s, &e, &op); modify(1, s, e, op); } printf("Case %d: The total value of the hook is %d.\n", ca++, query(1, 1, n)); } }这道题是线段树区间修改，区间查询的一个简单应用，关于线段树的知识点详情请见某大佬博客 这道题是sum来存储当前区间的总和，同时add标记即为懒标记（延迟标记），该标记暂时存储着这一区间中的一个操作，但暂时不把该操作下放，等到询问到下面的点时，在把这个操作往下执行，这就是懒标记的一个思路。 然后具体说说这道题的维护，这道题主要时维护区间和，那么首先更新用的pushup就应该写成当父结点等于连个子结点之和。然后pushdown（即对懒标记的处理）写成对子区间内的元素替换成add。对于查询，我们每次都看看当前有没有懒标记，有就往下传，然后往下找子结点，不断地返回总和。而对于修改则每次往下处理知道当前区间为处理区间的子集时，就可以停下了，并处理其懒标记。 在做题时，注意初始化。
