本文共 2130 字，大约阅读时间需要 7 分钟。
给n个数，默认为1，q次操作，将x-y内的数改成1-3中的一种。
求n个数的和。
线段树，区间更新。
#include #include #include #include #include using namespace std;typedef long long LL;const int MAXN = 1e5 + 10;int segments[MAXN * 4];int add[MAXN * 4];void Push_down(int root, int l, int r){ if (add[root]) { add[root << 1] = add[root]; add[root << 1 | 1] = add[root]; int mid = (l + r) / 2; segments[root << 1] = add[root] * (mid - l + 1); segments[root << 1 | 1] = add[root] * (r - mid); add[root] = 0; }}void Build_tree(int root, int l, int r){ if (l == r) { segments[root] = 1; return ; } int mid = (l + r) / 2; Build_tree(root << 1, l, mid); Build_tree(root << 1 | 1, mid + 1, r); segments[root] = segments[root << 1] + segments[root << 1 | 1];}void Update_tree(int root, int l, int r, int ql, int qr, int c){ if (ql > r || qr < l) return ; if (ql <= l && r <= qr) { segments[root] = (r - l + 1) * c; add[root] = c; } else { Push_down(root, l, r); int mid = (l + r) / 2; Update_tree(root << 1, l, mid, ql, qr, c); Update_tree(root << 1 | 1, mid + 1, r, ql, qr, c); segments[root] = segments[root << 1] + segments[root << 1 | 1]; }}int Query(int root, int l, int r, int w){ if (l == r) return segments[root]; int mid = (l + r) / 2; if (w <= mid) return Query(root << 1, l, mid, w); else return Query(root << 1 | 1, mid + 1, r, w);}int main(){ int t, cnt = 0; scanf("%d", &t); while (t--) { int n, q; int l, r, op; scanf("%d%d", &n, &q); Build_tree(1, 1, n); memset(add, 0, sizeof(add)); for (int i = 1;i <= q;i++) { scanf("%d%d%d", &l, &r, &op); Update_tree(1, 1, n, l, r, op); } printf("Case %d: The total value of the hook is %d.\n", ++cnt, segments[1]); } return 0;}
转载于:https://www.cnblogs.com/YDDDD/p/10426662.html