title: 题目 給定 N, Q，代表序列有 N 個元素，他們的初始值皆是 1。 接下來 Q 行，每行有三個數字 X, Y, Z，代表將序列中 X 到 Y 的元素值改成 Z。 最後輸出序列元素的和。
多組測資，第一個數字 T 代表有幾組測資。 對於每一組測資，第一行會輸入一個數字 N (1<=N<=100,000)，下一行會輸入一個數字 Q (0<=Q<=100,000)。 接下來 Q 行，每行有三個數字 X, Y, Z (1<=X<=Y<=N, 1<=Z<=3)
對於每一筆測資，輸出一個數字代表序列每個元素的總和，格式請參考範例輸出 title: 思路
直接用线段树模拟更新该节点即其所有子节点会超时。 使用lazy技巧, 若更新到 `[0,5]` 节点时, 就在该节点打上一个`lazy = Z`的标记, 同时停止向下继续更新, 直接返回。 等到某一次又更新到 `[0,5]` 节点时, 且不是最终要找的节点, 说明需要用到该节点之后的节点, 那么就需要将上次存的lacy更新到直系子节点, 同样也不必一次更新全部子节点, 只更新自己的直系两个就行, 这两个用到那个后面会再次进行这个过程。
就这样可以优化很多时间复杂度。 title:代码 ~~~ c ++ #include <cstring> #include <cstdio> #include <algorithm> using namespace std; #define lson l, mid, u << 1 #define rson mid + 1, r, u << 1 | 1 #define MID l + r >> 1 const int N = 1e5 + 10; int readInt() { int t; scanf("%d", &t); return t; }
struct node { int l, r; int val, lazy; } t[N << 2];
void pushup(int u) { t[u].val = t[u << 1].val + t[u << 1 | 1].val; }
void build(int l, int r, int u = 1) { t[u] = {l, r, 1, 0}; if (l == r) return; int mid = MID; build(lson), build(rson); pushup(u); }
void pushdown(node &op, int lazy) { op.val = lazy * (op.r - op.l + 1); op.lazy = lazy; }
void pushdown(int u) { if (!t[u].lazy) return; pushdown(t[u << 1], t[u].lazy); pushdown(t[u << 1 | 1], t[u].lazy); t[u].lazy = 0; }
void modify(int l, int r, int c, int u = 1) { if (l <= t[u].l && r >= t[u].r) // 当节点在所需区间内 { pushdown(t[u], c); // 更新该节点的总和, 且置lazy为更新值 return; } pushdown(u); // 此时所需区间在该节点里面, 即需要用到该节点的子节点, 则去清除该节点的lazy, 让子节点的值加上lazy // 注意也不是把下面所有子节点全给更新, 只更新直系子节点, 后面用到会重复这个操作 int mid = t[u].l + t[u].r >> 1; if (l <= mid) modify(l, r, c, u << 1); if (r > mid) modify(l, r, c, u << 1 | 1); pushup(u); }
int main() { int T = readInt(); for (int kase = 1; kase <= T; kase++) { int n = readInt(), m = readInt(); build(1, n); while (m--) // l, r, c { int l, r, c; scanf("%d %d %d", &l, &r, &c); modify(l, r, c); } printf("Case %d: The total value of the hook is %d.\n", kase, t[1].val); } return 0; } ~~~