看见网上说的延迟标记,lazy标记开始有点怵头。在纸上模拟一下发现只是在区间改值之后先不急于向下更新,当访问到该结点的时候再进行更新,很巧妙的方法。
/****************************************************/ #include <iostream> #include <cstring> #include <cstdio> #include <cstdlib> #include <cmath> #include <cctype> #include <stack> #include <map> #include <queue> #include <algorithm> #include <ctime> #define EPS 1E-8 #define MAXN 100010 #define INF (~0U >> 2) #define MOD 1000000007 #define Lson l, mid, rt << 1 #define Rson mid + 1, r, rt << 1 | 1 using namespace std; typedef long long LL; /****************************************************/ int num[MAXN << 2], col[MAXN << 2]; void push_up(int rt) { num[rt] = num[rt << 1] + num[rt << 1 | 1]; } void push_down(int rt, int m) { if (col[rt]) { col[rt << 1] = col[rt << 1 | 1] = col[rt]; num[rt << 1] = (m - (m >> 1)) * col[rt]; num[rt << 1 | 1] = (m >> 1) * col[rt]; col[rt] = 0; } } void build(int l, int r, int rt) { col[rt] = 0; if (l == r) { num[rt] = 1; return; } int mid = (l + r) >> 1; build(Lson); build(Rson); push_up(rt); } void update(int L, int R, int c, int l, int r, int rt) { if (L <= l && r <= R) { col[rt] = c; num[rt] = (r - l + 1) * c; return; } push_down(rt, r - l + 1); int mid = (l + r) >> 1; if (L <= mid) update(L, R, c, Lson); if (R > mid) update(L, R, c, Rson); push_up(rt); } int main() { int t, now = 0; scanf("%d", &t); while (t--) { int n; scanf("%d", &n); build(1, n, 1); int q; scanf("%d", &q); while(q--) { int a, b, c; scanf("%d%d%d", &a, &b, &c); update(a, b, c, 1, n, 1); } printf("Case %d: The total value of the hook is %d.\n", ++now, num[1]); } }