树状数组和线段树专题题解逆序对、区间异或、数线段差分、RMQ、最长连续交替子串、时间轴线段树

P1908(逆序对：归并排序/树状数组+离散化) 1h

1.只会暴力，半小时想不出正解；
2.老师讲了个归并排序的思路：合并的时候，如果左边的大右边的小，逆序对个数就是从左指针到mid的区间长度，证明不知道；
3.又讲了树状数组，是从暴力改过来的。最基本的是暴力枚举，然后内层可以优化为每次把c[a[i]]++，下一层循环时j从1枚举到a[i]，每次加上c[j]，这样就是逆序对数量了。然后就可以用树状数组优化了。
代码如下：

#include <bits/stdc++.h> #define int long long #define lowbit(x) x & (-x) using namespace std; int n, a[500010], b[500010], c[500010], sum = 0; void update(int x, int k) { for (int i = x; i <= n; i += lowbit(i)) c[i] += k; } int query(int x) { int ans = 0; for (int i = x; i >= 1; i -= lowbit(i)) ans += c[i]; return ans; } signed main() { scanf("%lld", &n); for (int i = 1; i <= n; i++) { scanf("%lld", a + i); b[i] = a[i]; } sort(b + 1, b + 1 + n); for (int i = 1; i <= n; i++) { int j = lower_bound(b + 1, b + 1 + n, a[i]) - b; a[i] = j; } for (int i = 1; i <= n; i++) { sum += i - 1 - query(a[i]); update(a[i], 1); } printf("%lld", sum); }

P1637(逆序对) 1h

1.先打个暴力，半天没有任何优化思路；
2.正解：循环j，求j前后各自的正序对数量，乘起来求和就OK。
代码如下：

#include <bits/stdc++.h> #define int long long #define lowbit(x) x & (-x) using namespace std; int n, a[500010], b[500010], c[500010], ans[500010][2], sum = 0; void update(int x, int k) { for (int i = x; i <= n; i += lowbit(i)) c[i] += k; } int query(int x) { int qzh = 0; for (int i = x; i >= 1; i -= lowbit(i)) qzh += c[i]; return qzh; } signed main() { scanf("%lld", &n); for (int i = 1; i <= n; i++) { scanf("%lld", &a[i]); b[i] = a[i]; } sort(b + 1, b + 1 + n); for (int i = 1; i <= n; i++) { a[i] = lower_bound(b + 1, b + 1 + n, a[i]) - b; } for (int i = 1; i <= n; i++) { ans[i][0] = query(a[i] - 1); update(a[i], 1); } memset(c, 0, sizeof c); for (int i = n; i >= 1; i--) { ans[i][1] = n - i - query(a[i]); update(a[i], 1); } for (int i = 1; i <= n; i++) { sum += ans[i][0] * ans[i][1]; } printf("%lld", sum); }

P3870(区间异或：线段树) 0.5h

1.有个新奇的想法。可以把线段树视为DP，tree[i]/lazy[i]相当于状态，pushdown/update/query相当于转移，外加边界；
2.定状态：tree[i]表示i管辖的区间开着的个数，lazy[i]表示i管辖的区间操作次数的奇偶；
3.定转移：如果lazy[i]为1那么tree[i<<1]以及tree[i<<1|1]都变成len - sum，lazy[i << 1]和lazy[i << 1 | 1]取反，lazy[i]清空；
4.处理边界：边界时，直接修改tree[i]为len - sum，lazy[i]取反。
代码如下：

#include <bits/stdc++.h> #define MAXN 400010 #define int long long using namespace std; int n, m, c, a, b, tree[MAXN], lazy[MAXN]; void pushdown(int u, int l, int r, int mid) { if (lazy[u]) { tree[u << 1] = mid - l + 1 - tree[u << 1]; tree[u << 1 | 1] = r - mid - tree[u << 1 | 1]; lazy[u << 1] = !lazy[u << 1]; lazy[u << 1 | 1] = !lazy[u << 1 | 1]; lazy[u] = 0; } } void update(int u, int l, int r, int x, int y) { if (l >= x && r <= y) { tree[u] = (r - l + 1) - tree[u]; lazy[u] = !lazy[u]; return; } int mid = (l + r) >> 1; pushdown(u, l, r, mid); if (mid >= x) update(u << 1, l, mid, x, y); if (mid < y) update(u << 1 | 1, mid + 1, r, x, y); tree[u] = tree[u << 1] + tree[u << 1 | 1]; } int query(int u, int l, int r, int x, int y) { int sum = 0; if (l >= x && r <= y) { return tree[u]; } int mid = (l + r) >> 1; pushdown(u, l, r, mid); if (mid >= x) sum += query(u << 1, l, mid, x, y); if (mid < y) sum += query(u << 1 | 1, mid + 1, r, x, y); return sum; } signed main() { scanf("%lld%lld", &n, &m); while (m--) { scanf("%lld%lld%lld", &c, &a, &b); if (!c) update(1, 1, n, a, b); else printf("%lld\n", query(1, 1, n, a, b)); } }

P1438(线段树+数学) 0.6h

1.状态：tree[u]表示u管辖区间的数列之和，lazyk[u]表示之前积累的首项，lazyd[u]表示之前积累的公差；
2.转移：tree[u<<1]增加S(l,mid)，tree[u<<1|1]增加S(mid+1,r)，lazyk[u<<1]增加lazyk[u]，lazyk[u<<1|1]增加lazyk[u] + (mid - l + 1) * d，lazyd[u<<1(|1)]增加lazyd[u]，lazyk[u]和lazyd[u]清零；
3.边界：tree[u]增加S(l,r)，lazyk[u]增加k，lazyd[u]增加d；
4.调了半天一直WA，只好喂了DS纠了点错。
代码如下：

#include <bits/stdc++.h> #define MAXN 400010 #define int long long using namespace std; int n, m, op, l, r, K, D, p, a[MAXN], tree[MAXN], lazyk[MAXN], lazyd[MAXN]; inline int sigma(int x, int y, int k, int d) { return (y - x + 1) * k + (y - x) * (y - x + 1) * d / 2; } inline void pushdown(int u, int l, int r, int mid) { if (lazyk[u] || lazyd[u]) { tree[u << 1] += sigma(l, mid, lazyk[u], lazyd[u]); tree[u << 1 | 1] += sigma(mid + 1, r, lazyk[u] + (mid - l + 1) * lazyd[u], lazyd[u]); lazyk[u << 1] += lazyk[u]; lazyk[u << 1 | 1] += lazyk[u] + (mid - l + 1) * lazyd[u]; lazyd[u << 1] += lazyd[u]; lazyd[u << 1 | 1] += lazyd[u]; lazyk[u] = lazyd[u] = 0; } } inline void update(int u, int l, int r, int x, int y, int k, int d) { if (l >= x && r <= y) { tree[u] += sigma(l, r, k + (l - x) * d, d); lazyk[u] += k + (l - x) * d; lazyd[u] += d; return; } int mid = (l + r) >> 1; pushdown(u, l, r, mid); if (mid >= x) update(u << 1, l, mid, x, y, k, d); if (mid < y) update(u << 1 | 1, mid + 1, r, x, y, k, d); tree[u] = tree[u << 1] + tree[u << 1 | 1]; } inline int query(int u, int l, int r, int x, int y) { int sum = 0; if (l >= x && r <= y) { return tree[u]; } int mid = (l + r) >> 1; pushdown(u, l, r, mid); if (mid >= x) sum += query(u << 1, l, mid, x, y); if (mid < y) sum += query(u << 1 | 1, mid + 1, r, x, y); return sum; } signed main() { scanf("%lld%lld", &n, &m); for (int i = 1; i <= n; i++) { scanf("%lld", a + i); update(1, 1, n, i, i, a[i], 0); } while (m--) { scanf("%lld", &op); if (op == 1) { scanf("%lld%lld%lld%lld", &l, &r, &K, &D); update(1, 1, n, l, r, K, D); } else { scanf("%lld", &p); printf("%lld\n", query(1, 1, n, p, p)); } } }

P1558(线段树) 0.6h

1.数据范围是个好东西。因为T<=30，所以我们可以开30个线段树(●'◡'●)；
2.状态：tree[i][u]表示第i个线段树的u节点管辖区间是否有该颜色，lazy[i][u]表示u节点管辖区间上一次是否涂了该颜色；
3.转移和边界太复杂，参见代码。
代码如下：

#include <bits/stdc++.h> #define N 400010 #define int long long using namespace std; int L, T, O, A, B, C; char op, lazy[31][N]; bool tree[31][N]; //tree[i][u]：u节点所管区间有无第i种颜色 //lazy[i][u]：u节点需要向下删除/不传/增加第i种颜色 void pushdown(int i, int o, int l, int r, int mid) { if (l == r) return; if (lazy[i][o] == -1) { tree[i][o << 1] = tree[i][o << 1 | 1] = 0; lazy[i][o << 1] = lazy[i][o << 1 | 1] = -1; lazy[i][o] = 0; } if (lazy[i][o] == 1) { tree[i][o << 1] = tree[i][o << 1 | 1] = lazy[i][o << 1] = lazy[i][o << 1 | 1] = 1; lazy[i][o] = 0; } } void update(int i, int o, int l, int r, int x, int y, bool flg) { if (l >= x && r <= y) { if (flg) { tree[i][o] = lazy[i][o] = 1; } else { tree[i][o] = 0; lazy[i][o] = -1; } return; } int mid = (l + r) / 2; pushdown(i, o, l, r, mid); if (mid >= x) update(i, o << 1, l, mid, x, y, flg); if (mid < y) update(i, o << 1 | 1, mid + 1, r, x, y, flg); tree[i][o] = tree[i][o << 1] | tree[i][o << 1 | 1]; } bool query(int i, int o, int l, int r, int x, int y) { bool ans = 0; if (l >= x && r <= y) { return tree[i][o]; } int mid = (l + r) / 2; pushdown(i, o, l, r, mid); if (mid >= x) ans |= query(i, o << 1, l, mid, x, y); if (mid < y) ans |= query(i, o << 1 | 1, mid + 1, r, x, y); return ans; } signed main() { scanf("%lld%lld%lld", &L, &T, &O); for (int i = 1; i <= L; i++) { update(1, 1, 1, L, i, i, 1); } while (O--) { cin >> op; scanf("%lld%lld", &A, &B); if (A > B) swap(A, B); if (op == 'C') { scanf("%lld", &C); for (int i = 1; i <= T; i++) { if (i == C) update(i, 1, 1, L, A, B, 1); else update(i, 1, 1, L, A, B, 0); } } else { int sum = 0; for (int i = 1; i <= T; i++) { if (query(i, 1, 1, L, A, B)) sum++; } printf("%lld\n", sum); } } }

P2184(树状数组+差分数线段) 0.6h

1.思维题：正难则反，可以利用差分，求出没有的种类数，再用总数减，开两个树状数组完事；
2.求法(偷看ed下题解)：y前面的左端点总数 - x-1前面的右端点总数即为答案，因为这就表示x ~ y之间的左端点数，也就是区间内的地雷数量。
3.充分性：令区间内左端点数为n，则可知这n种地雷一定在区间内；必要性：在区间内的地雷数量为n，则它们的左端点一定都在区间内数量为n。
代码如下：

#include <bits/stdc++.h> #define int long long #define lowbit(x) x&(-x) using namespace std; int n, m, b, x, y; int c[2][100010]; void update(int flg, int x, int k) { for (int i = x; i <= n; i += lowbit(i)) c[flg][i] += k; } int query(int flg, int x) { int sum = 0; for (int i = x; i >= 1; i -= lowbit(i)) sum += c[flg][i]; return sum; } signed main() { scanf("%lld%lld", &n, &m); while (m--) { scanf("%lld%lld%lld", &b, &x, &y); if (b == 1) { update(0, x, 1); update(1, y, 1); } else { int ans = query(0, y) - query(1, x - 1); printf("%lld\n", ans); } } return 0; }

P1531(RMQ：线段树)

一道无需lazy的点修区查问题
1.状态：tree[o]表示o子树所辖区间的最大值；
2.转移：tree[o] = max(tree[o<<1], tree[o<<1|1])。
代码如下：

#include <bits/stdc++.h> #define N 800010 #define int long long using namespace std; int n, m, u, v, a[N], tree[N]; char op; void update(int o, int l, int r, int x, int k) { if (l >= x && r <= x) { tree[o] = k; return; } int mid = (l + r) / 2; if (x <= mid) update(o << 1, l, mid, x, k); else update(o << 1 | 1, mid + 1, r, x, k); tree[o] = max(tree[o << 1], tree[o << 1 | 1]); } int query(int o, int l, int r, int x, int y) { if (l >= x && r <= y) return tree[o]; int mid = (l + r) / 2, ans = 0; if (x <= mid) ans = max(ans, query(o << 1, l, mid, x, y)); if (y > mid) ans = max(ans, query(o << 1 | 1, mid + 1, r, x, y)); return ans; } signed main() { scanf("%lld%lld", &n, &m); for (int i = 1; i <= n; i++) { scanf("%lld", a + i); update(1, 1, n, i, a[i]); } while (m--) { cin >> op; scanf("%lld%lld", &u, &v); if (op == 'U') { if (query(1, 1, n, u, u) < v) { update(1, 1, n, u, v); } } else { printf("%lld\n", query(1, 1, n, u, v)); } } }

B4374(RMQ+DFS序)

把树转化成DFS序数组，然后P2184即可。
代码如下：

#include <bits/stdc++.h> #define N 800010 #define int long long using namespace std; int n, m, u, v, w, op, tms = 0, ans = 0, a[200010], dfso[200010], kid[200010], tree[N], lazy[N]; vector<int> g[200010]; void dfs(int u, int pa) { dfso[u] = ++tms; kid[u] = 1; for (int v : g[u]) { if (v == pa) continue; dfs(v, u); kid[u] += kid[v]; } } void update(int o, int l, int r, int x, int k) { if (l >= x && r <= x) { tree[o] = k; return; } int mid = (l + r) / 2; if (mid >= x) update(o << 1, l, mid, x, k); if (mid < x) update(o << 1 | 1, mid + 1, r, x, k); tree[o] = max(tree[o << 1], tree[o << 1 | 1]); } int query(int o, int l, int r, int x, int y) { int ans = 0; if (l >= x && r <= y) { return tree[o]; } int mid = (l + r) / 2; if (mid >= x) ans = max(ans, query(o << 1, l, mid, x, y)); if (mid < y) ans = max(ans, query(o << 1 | 1, mid + 1, r, x, y)); return ans; } signed main() { scanf("%lld%lld", &n, &m); for (int i = 1; i <= n; i++) { scanf("%lld", a + i); } for (int i = 1; i < n; i++) { scanf("%lld%lld", &u, &v); g[u].push_back(v); g[v].push_back(u); } dfs(1, 0); for (int i = 1; i <= n; i++) { update(1, 1, n, dfso[i], a[i]); } for (int i = 1; i <= m; i++) { scanf("%lld%lld", &op, &u); if (op == 1) { scanf("%lld", &w); update(1, 1, n, dfso[u], w); } else { printf("%lld\n", query(1, 1, n, dfso[u], dfso[u] + kid[u] - 1)); } } }

P1253(线段树)

1.状态：tree[o]表示区间最大值，lazy_set[o]表示上一次修改的值，lazy_add[o]表示上一次增加的值；
2.转移：进行一系列分类讨论pushdown。
代码如下：

#include <bits/stdc++.h> #define N 4000100 #define int long long #define inf 1e11 using namespace std; int n, m, a, x, y, k, op, tree[N], lazy_set[N], lazy_add[N], ans; void pushdown(int o, int l, int r, int mid) { if (lazy_set[o] != inf) { lazy_set[o << 1] = lazy_set[o << 1 | 1] = tree[o << 1] = tree[o << 1 | 1] = lazy_set[o]; lazy_add[o << 1] = lazy_add[o << 1 | 1] = 0; lazy_set[o] = inf; } if (lazy_add[o] != 0) { lazy_add[o << 1] += lazy_add[o]; lazy_add[o << 1 | 1] += lazy_add[o]; tree[o << 1] += lazy_add[o]; tree[o << 1 | 1] += lazy_add[o]; lazy_add[o] = 0; } } void update_add(int o, int l, int r, int x, int y, int k) { if (l >= x && r <= y) { tree[o] += k; lazy_add[o] += k; return; } int mid = (l + r) / 2; pushdown(o, l, r, mid); if (mid >= x) update_add(o << 1, l, mid, x, y, k); if (mid < y) update_add(o << 1 | 1, mid + 1, r, x, y, k); tree[o] = max(tree[o << 1], tree[o << 1 | 1]); } void update_set(int o, int l, int r, int x, int y, int k) { if (l >= x && r <= y) { lazy_set[o] = k; lazy_add[o] = 0; tree[o] = k; return; } int mid = (l + r) / 2; pushdown(o, l, r, mid); if (mid >= x) update_set(o << 1, l, mid, x, y, k); if (mid < y) update_set(o << 1 | 1, mid + 1, r, x, y, k); tree[o] = max(tree[o << 1], tree[o << 1 | 1]); } int query(int o, int l, int r, int x, int y) { int ans = -inf; if (l >= x && r <= y) { return tree[o]; } int mid = (l + r) / 2; pushdown(o, l, r, mid); if (mid >= x) ans = max(ans, query(o << 1, l, mid, x, y)); if (mid < y) ans = max(ans, query(o << 1 | 1, mid + 1, r, x, y)); return ans; } signed main() { for (int i = 0; i <= N; i++) { lazy_set[i] = inf; } scanf("%lld%lld", &n, &m); for (int i = 1; i <= n; i++) { scanf("%lld", &a); update_set(1, 1, n, i, i, a); } while (m--) { scanf("%lld%lld%lld", &op, &x, &y); if (op == 1) { scanf("%lld", &k); update_set(1, 1, n, x, y, k); } else if (op == 2) { scanf("%lld", &k); update_add(1, 1, n, x, y, k); } else { printf("%lld\n", query(1, 1, n, x, y)); } } }

P6492(最长连续交替子串：线段树)

1.状态：记录suf[o]，pre[o]；tree[o]表示区间满足长度——点修，无需lazy和query函数；
2.转移：简简单单无需pushdown，BUT！！！要进行行一系列pushup。
代码如下：

#include <bits/stdc++.h> #define N 800010 #define int long long using namespace std; int n, q, x, suf[N], pre[N], tree[N]; bool a[N]; void pushup(int o, int l, int r, int mid) { suf[o] = suf[o << 1 | 1]; pre[o] = pre[o << 1]; tree[o] = max(tree[o << 1], tree[o << 1 | 1]); int left = mid - l + 1, right = r - mid; if (a[mid] != a[mid + 1]) { if (suf[o << 1 | 1] == right) { suf[o] = right + suf[o << 1]; } if (pre[o << 1] == left) { pre[o] = left + pre[o << 1 | 1]; } tree[o] = max(tree[o], suf[o << 1] + pre[o << 1 | 1]); } } void update(int o, int l, int r, int pos) { if (l == r) { tree[o] = 1; a[pos] ^= 1; pre[o] = 1; suf[o] = 1; return; } int mid = (l + r) / 2; if (mid >= pos) update(o << 1, l, mid, pos); else update(o << 1 | 1, mid + 1, r, pos); pushup(o, l, r, mid); } signed main() { for (int i = 1; i < N; i++) pre[i] = suf[i] = tree[i] = 1; scanf("%lld%lld", &n, &q); while (q--) { scanf("%lld", &x); update(1, 1, n, x); printf("%lld\n", tree[1]); } }

P4588(时间轴线段树)

所有均初始化为1，然后只需要把输入的次序转化为线段树管辖的数组下标，如果是乘那么这一位就修改为乘的数，除回来就把它修改回1，之后进行点修区查即可。
代码如下：

#include <bits/stdc++.h> #define N 400010 #define int long long using namespace std; int t, Q, M, m, op, tree[N]; void update(int o, int l, int r, int x, int k) { if (l >= x && r <= x) { tree[o] = k; return; } int mid = (l + r) / 2; if (mid >= x) update(o << 1, l, mid, x, k); if (mid < x) update(o << 1 | 1, mid + 1, r, x, k); tree[o] = (tree[o << 1] * tree[o << 1 | 1]) % M; } int query(int o, int l, int r, int x, int y) { int ans = 1; if (l >= x && r <= y) { return tree[o]; } int mid = (l + r) / 2; if (mid >= x) ans = (ans * query(o << 1, l, mid, x, y)) % M; if (mid < y) ans = (ans * query(o << 1 | 1, mid + 1, r, x, y)) % M; return ans; } signed main() { scanf("%lld", &t); while (t--) { memset(tree, 0, sizeof tree); scanf("%lld%lld", &Q, &M); for (int i = 1; i <= Q; i++) { update(1, 1, Q, i, 1); } for (int i = 1; i <= Q; i++) { scanf("%lld%lld", &op, &m); if (op == 1) { update(1, 1, Q, i, m); printf("%lld\n", query(1, 1, Q, 1, i)); } else { update(1, 1, Q, m, 1); printf("%lld\n", query(1, 1, Q, 1, i)); } } } }

P3373(线段树)

“模板题”

代码如下：

#include <bits/stdc++.h> #define N 400010 #define int long long using namespace std; int n, q, m, a, x, y, k, op, tree[N], lazy_mul[N], lazy_add[N]; void pushdown(int o, int l, int r, int mid) { lazy_mul[o << 1] = (lazy_mul[o << 1] * lazy_mul[o]) % m; lazy_mul[o << 1 | 1] = (lazy_mul[o << 1 | 1] * lazy_mul[o]) % m; lazy_add[o << 1] = (lazy_add[o << 1] * lazy_mul[o]) % m; lazy_add[o << 1 | 1] = (lazy_add[o << 1 | 1] * lazy_mul[o]) % m; tree[o << 1] = (tree[o << 1] * lazy_mul[o]) % m; tree[o << 1 | 1] = (tree[o << 1 | 1] * lazy_mul[o]) % m; lazy_mul[o] = 1; lazy_add[o << 1] = (lazy_add[o << 1] + lazy_add[o]) % m; lazy_add[o << 1 | 1] = (lazy_add[o << 1 | 1] + lazy_add[o]) % m; tree[o << 1] = (tree[o << 1] + (mid - l + 1) * lazy_add[o]) % m; tree[o << 1 | 1] = (tree[o << 1 | 1] + (r - mid) * lazy_add[o]) % m; lazy_add[o] = 0; } void update_mul(int o, int l, int r, int x, int y, int k) { if (l >= x && r <= y) { tree[o] = (tree[o] * k) % m; lazy_mul[o] = (lazy_mul[o] * k) % m; lazy_add[o] = (lazy_add[o] * k) % m; return; } int mid = (l + r) / 2; pushdown(o, l, r, mid); if (mid >= x) update_mul(o << 1, l, mid, x, y, k); if (mid < y) update_mul(o << 1 | 1, mid + 1, r, x, y, k); tree[o] = (tree[o << 1] + tree[o << 1 | 1]) % m; } void update_add(int o, int l, int r, int x, int y, int k) { if (l >= x && r <= y) { lazy_add[o] = (lazy_add[o] + k) % m; tree[o] = (tree[o] + (r - l + 1) * k) % m; return; } int mid = (l + r) / 2; pushdown(o, l, r, mid); if (mid >= x) update_add(o << 1, l, mid, x, y, k); if (mid < y) update_add(o << 1 | 1, mid + 1, r, x, y, k); tree[o] = (tree[o << 1] + tree[o << 1 | 1]) % m; } int query(int o, int l, int r, int x, int y) { int ans = 0; if (l >= x && r <= y) { return tree[o]; } int mid = (l + r) / 2; pushdown(o, l, r, mid); if (mid >= x) ans = (ans + query(o << 1, l, mid, x, y)) % m; if (mid < y) ans = (ans + query(o << 1 | 1, mid + 1, r, x, y)) % m; return ans % m; } signed main() { for (int i = 1; i < N; i++) lazy_mul[i] = 1; scanf("%lld%lld%lld", &n, &q, &m); for (int i = 1; i <= n; i++) { scanf("%lld", &a); update_add(1, 1, n, i, i, a); } for (int i = 1; i <= q; i++) { scanf("%lld%lld%lld", &op, &x, &y); if (op == 1) { scanf("%lld", &k); update_mul(1, 1, n, x, y, k); } else if (op == 2) { scanf("%lld", &k); update_add(1, 1, n, x, y, k); } else { printf("%lld\n", query(1, 1, n, x, y)); } } }