【学习笔记】线段树

## 例题 [P2023](https://www.luogu.org/problemnew/show/P2023) 就是这个线段树2的模板，我总是没有AC过，这次终于是AC了！ 最需要注意的是：**在乘的时候，加法的$lazytag$也必须跟着更新；$pushdown$的时候，加法的$lazytag$也必须跟着更新**，不然就无法连续维护加操作和乘操作。 ```cpp #include<bits/stdc++.h> #define LL long long using namespace std; const int MAXN = 100010; struct SEGTREE { int l, r; LL v, add, mul; } segtree[MAXN<<2]; int n, p, m; LL a[MAXN]; void build_tree(int num, int l, int r) { segtree[num].l = l; segtree[num].r = r; segtree[num].add = 0; segtree[num].mul = 1; if(l == r) { segtree[num].v = (LL)a[l] % p; return; } int mid = (l + r) >> 1; build_tree(num<<1, l, mid); build_tree(num<<1|1, mid+1, r); segtree[num].v = (segtree[num<<1].v + segtree[num<<1|1].v) % p; return; } void pushdown(int num) { int lson = num<<1, rson = num<<1|1; segtree[lson].v = (segtree[lson].v * segtree[num].mul + (segtree[num].add * (segtree[lson].r - segtree[lson].l + 1))) % p; segtree[rson].v = (segtree[rson].v * segtree[num].mul + (segtree[num].add * (segtree[rson].r - segtree[rson].l + 1))) % p; segtree[lson].add = (segtree[lson].add * segtree[num].mul + segtree[num].add) % p; segtree[rson].add = (segtree[rson].add * segtree[num].mul + segtree[num].add) % p; segtree[lson].mul = (segtree[lson].mul * segtree[num].mul) % p; segtree[rson].mul = (segtree[rson].mul * segtree[num].mul) % p; segtree[num].add = 0; segtree[num].mul = 1; return; } void edit_tree(bool add, int num, int l, int r, int c) { int ll = segtree[num].l, rr = segtree[num].r; if(add) { if(ll >= l && rr <= r) { segtree[num].v = (segtree[num].v + (c * (rr - ll + 1))) % p; segtree[num].add = (segtree[num].add + c) % p; return; } pushdown(num); int mid = (ll + rr) >> 1; if(l <= mid) edit_tree(add, num<<1, l, r, c); if(r > mid) edit_tree(add, num<<1|1, l, r, c); segtree[num].v = (segtree[num<<1].v + segtree[num<<1|1].v) % p; } else { if(ll >= l && rr <= r) { segtree[num].v = (segtree[num].v * c) % p; segtree[num].mul = (segtree[num].mul * c) % p; segtree[num].add = (segtree[num].add * c) % p; return; } pushdown(num); int mid = (ll + rr) >> 1; if(l <= mid) edit_tree(add, num<<1, l, r, c); if(r > mid) edit_tree(add, num<<1|1, l, r, c); segtree[num].v = (segtree[num<<1].v + segtree[num<<1|1].v) % p; } return; } LL query(int num, int l, int r) { int ll = segtree[num].l, rr = segtree[num].r; if(ll >= l && rr <= r) return segtree[num].v % p; pushdown(num); int mid = (ll + rr) >> 1; LL sum = 0; if(l <= mid) sum = (query(num<<1, l, r) + sum) % p; if(r > mid) sum = (query(num<<1|1, l, r) + sum) % p; return sum; } int main() { scanf("%d%d", &n, &p); for(int i=1; i<=n; i++) scanf("%lli", &a[i]); build_tree(1, 1, n); int opt, t, g, c; scanf("%d", &m); while(m--) { scanf("%d", &opt); switch(opt) { case 1: { scanf("%d%d%d", &t, &g, &c); edit_tree(false, 1, t, g, c); break; } case 2: { scanf("%d%d%d", &t, &g, &c); edit_tree(true, 1, t, g, c); break; } case 3: { scanf("%d%d", &t, &g); printf("%lli\n", query(1, t, g)%p); break; } } } return 0; } ``` --- ## 易错点更新 $edit\_tree$以后记得合并儿子信息！ **$pushdown$及$edit\_tree$时记得要把$tag$乘上区间长** --- # 线段树维护区间修改/单点修改/区间最大值 ## 例题 [P4315](https://www.luogu.org/problemnew/show/P4315) 恶心死了，查半天错才知道自己错在哪里。 这里的线段树维护了两个懒标记：$tree[x].tag$以及$tree[x].c$。$tree[x].tag$维护的是区间加，而$tree[x].c$维护的是区间修改。在$pushdown$的时候就要慎重考虑这两个玩意儿的顺序了，结论是： ## 先看$\textbf{tree[x].c}$，再看$\textbf{tree[x].tag}$。 **注意：** 在$cover(l,r,c)$的时候，会使当前$tree[x].tag=0$，这也就是说**肯定是在一次$\textbf{cover(l,r,c)}$操作之后，出现的$\textbf{tree[x].tag}$才会对线段树造成修改**，因此在$pushdown$的时候，如果发生了$cover(l,r,c)$操作，即$tree[x].c\neq-1$,一定是先把$tree[x].c$下传，将两儿子的$tree[x].tag$清空，再把$tree[x].tag$信息下传。 此思路**非常重要**，正确决定线段树$lazytag$的下传顺序才不会懒出毛病。 ```cpp inline void pushdown(int x) { if(~tree[x].c) { tree[x<<1].max = tree[x<<1|1].max = tree[x].c; tree[x<<1].c = tree[x<<1|1].c = tree[x].c; tree[x<<1].tag = tree[x<<1|1].tag = 0; tree[x].c = -1; } if(tree[x].tag) { tree[x<<1].max += tree[x].tag; tree[x<<1|1].max += tree[x].tag; tree[x<<1].tag += tree[x].tag; tree[x<<1|1].tag += tree[x].tag; tree[x].tag = 0; } return; } ``` 相应地，我们已经决定了$lazytag$的下传顺序，那么$cover(l,r,c)$和$add(l,r,c)$也要按照这个规则来打懒标记，也就是说 **$\textbf{cover(l,r,c)}$的时候需要把$\textbf{tree[x].tag=0}$** ，而$add(l,r,c)$则不需要做出调整。 ```cpp inline void cover(int x, int l, int r, int c) { int ll = tree[x].l, rr = tree[x].r; if(l <= ll && rr <= r) { tree[x].max = tree[x].c = c; tree[x].tag = 0; return; } pushdown(x); int mid = (ll + rr) >> 1; if(l <= mid) cover(x<<1, l, r, c); if(r > mid) cover(x<<1|1, l, r, c); pushup(x); return; } inline void add(int x, int l, int r, int c) { int ll = tree[x].l, rr = tree[x].r; if(l <= ll && rr <= r) { tree[x].max += c; tree[x].tag += c; return; } pushdown(x); int mid = (ll + rr) >> 1; if(l <= mid) add(x<<1, l, r, c); if(r > mid) add(x<<1|1, l, r, c); pushup(x); return; } ``` **谨记**：慎重考虑懒标记的下传顺序、修改时打懒标记的规则！ --- 完整代码 ```cpp //code inline void pushdown(int x) { if(~tree[x].c) { tree[x<<1].max = tree[x<<1|1].max = tree[x].c; tree[x<<1].c = tree[x<<1|1].c = tree[x].c; tree[x<<1].tag = tree[x<<1|1].tag = 0; tree[x].c = -1; } if(tree[x].tag) { tree[x<<1].max += tree[x].tag; tree[x<<1|1].max += tree[x].tag; tree[x<<1].tag += tree[x].tag; tree[x<<1|1].tag += tree[x].tag; tree[x].tag = 0; } return; } inline void pushup(int x) { tree[x].max = max(tree[x<<1].max, tree[x<<1|1].max); return; } inline void build_tree(int x, int l, int r) { tree[x].l = l, tree[x].r = r; tree[x].tag = 0, tree[x].c = -1; if(l == r) { tree[x].max = w[rev[l]]; return; } int mid = (l + r) >> 1; build_tree(x<<1, l, mid); build_tree(x<<1|1, mid + 1, r); pushup(x); return; } inline void cover(int x, int l, int r, int c) { int ll = tree[x].l, rr = tree[x].r; if(l <= ll && rr <= r) { tree[x].max = tree[x].c = c; tree[x].tag = 0; return; } pushdown(x); int mid = (ll + rr) >> 1; if(l <= mid) cover(x<<1, l, r, c); if(r > mid) cover(x<<1|1, l, r, c); pushup(x); return; } inline void add(int x, int l, int r, int c) { int ll = tree[x].l, rr = tree[x].r; if(l <= ll && rr <= r) { tree[x].max += c; tree[x].tag += c; return; } pushdown(x); int mid = (ll + rr) >> 1; if(l <= mid) add(x<<1, l, r, c); if(r > mid) add(x<<1|1, l, r, c); pushup(x); return; } inline int query(int x, int l, int r) { int res = -INF; int ll = tree[x].l, rr = tree[x].r; if(l <= ll && rr <= r) return tree[x].max; pushdown(x); int mid = (ll + rr) >> 1; if(l <= mid) res = max(res, query(x<<1, l, r)); if(r > mid) res = max(res, query(x<<1|1, l, r)); return res; } ``` --- ## 例题 [P3740](https://www.luogu.org/problemnew/show/P3740) 这道题是维护区间染色。具体做法为直接开一个$clr[]$来维护当前区间有没有被完全覆盖。可以知道的是，如果一个海报所处的区间被后来的海报完全覆盖，那么这个海报就没法被看见了。例如：  图中$[3,4]$的这块海拔被遮完了，因此它没法被看见。 考虑将这个过程**离线**（在线的话可参考[树链剖分](https://ncc79601.blog.luogu.org/tree-chain-split)部分对[P2146](https://www.luogu.org/problem/P2146)的题解），那么每次只需要查询当前海报区间是否已经被完全覆盖就可以了。因为根本不需要建树，所以复杂度为稳定$O(logn)$，对付这个数据也足够了。 ```cpp #include <bits/stdc++.h> using namespace std; const int MAXN = 1e7 + 10, MAXM = 1e3 + 10; bool clr[MAXN << 2], flag; int n, m, a[MAXM], b[MAXM], ans = 0; void pushup(int x) { clr[x] = clr[x<<1] & clr[x<<1|1]; } void edit_tree(int x, int l, int r, int L, int R) { if(clr[x]) return; if(L <= l && r <= R) { flag = clr[x] = true; return; } int mid = (l + r) >> 1; if(L <= mid) edit_tree(x<<1, l, mid, L, R); if(R > mid) edit_tree(x<<1|1, mid + 1, r, L, R); pushup(x); } int main() { scanf("%d %d", &n, &m); for(int i = 1; i <= m; i++) scanf("%d %d", &a[i], &b[i]); for(int i = m; i; i--) { flag = false; edit_tree(1, 1, n, a[i], b[i]); if(flag) ans++; } printf("%d", ans); return 0; } ```