[BNUOJ] 超级线段树（离线，线段树）

题目链接：https://www.bnuoj.com/v3/problem_show.php?pid=49100

这题正着做会超时，考虑倒过来：

要求查询最后一次修改的值，那么某个区间的最后一次被修改，那之前的所有这个区间的子集的操作都是对查询没有贡献的。

所以倒过来区间更新线段树，tag来记录线段树某区间下的所有点的状态，更新标记的时候点的儿子有tag标记就不要修改。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define lrt rt << 1
 5 #define rrt rt << 1 | 1
 6 const int maxn = 1000100;
 7 const int maxm = maxn << 2;
 8 int n, m;
 9 int seg[maxm], tag[maxm];
10 int ll[maxn], rr[maxn], pp[maxn];
11 
12 void pushdown(int rt) {
13     if(tag[rt]) {
14         if(!tag[lrt]) tag[lrt] = tag[rt];
15         if(!tag[rrt]) tag[rrt] = tag[rt];
16         tag[rt] = 0;
17     }
18 }
19 
20 void update(int rt, int L, int R, int l, int r, int p) {
21     if(tag[rt]) return;
22     if(L <= l && r <= R) {
23         tag[rt] = p;
24         return;
25     }
26     pushdown(rt);
27     int m = (l + r) >> 1;
28     if(L <= m) update(lrt, L, R, l, m, p);
29     if(m < R) update(rrt, L, R, m+1, r, p);
30 }
31 
32 void query(int rt, int l, int r) {
33     if(l == r) {
34         printf("%d
", tag[rt]);
35         return;
36     }
37     pushdown(rt);
38     int m = (l + r) >> 1;
39     query(lrt, l, m); query(rrt, m+1, r);
40 }
41 
42 int main() {
43     // freopen("in", "r", stdin);
44     int T, l, r, p;
45     scanf("%d", &T);
46     while(T--) {
47         scanf("%d%d",&n,&m);
48         memset(tag, 0, sizeof(tag));
49         for(int i = 0; i < m; i++) scanf("%d%d%d",&ll[i],&rr[i],&pp[i]);
50         for(int i = m - 1; i >= 0; i--) update(1, ll[i], rr[i], 1, n, pp[i]);
51         query(1, 1, n);
52     }
53     return 0;
54 }