数据结构专题2 - step 1

三维的空间中有 $n$ 个元素，初始时每个空间元素均为0。更新操作是0变1，1变0，是一个立方体型区域内的所有元素都更新。然后查询是问某个点的元素是0还是1. ($1<=n<=100,m<=10000$)

三维树状数组，维护三维差分数组，所有加法减法都是异或，就可以了。

对于 $n$ 维差分或者是 $n$ 维前缀和，公式一定有 $2^n$ 项，根据 $x_2,y_2,z_2...$ 这些东西出现次数的奇偶性就可以判断出来符号了.

#include<bits/stdc++.h>
using namespace std;
const int N = 110;
int tr[N][N][N];
int n, m;
int lowbit(int x)
{return x & -x;
}
void add(int x, int y, int z)
{for(int i = x; i <= n; i += lowbit(i)){for(int j = y; j <= n; j += lowbit(j)){for(int k = z; k <= n; k += lowbit(k)){tr[i][j][k] ^= 1;}}}
}
int sum(int x, int y, int z)
{int res = 0;for(int i = x; i; i -= lowbit(i)){for(int j = y; j; j -= lowbit(j)){for(int k = z; k; k -= lowbit(k)){res ^= tr[i][j][k];}}}return res;
}
void modify(int x1, int y1, int z1, int x2, int y2, int z2)
{add(x1, y1, z1);add(x1, y1, z2 + 1);add(x1, y2 + 1, z1);add(x1, y2 + 1, z2 + 1);add(x2 + 1, y1, z1);add(x2 + 1, y1, z2 + 1);add(x2 + 1, y2 + 1, z1);add(x2 + 1, y2 + 1, z2 + 1);
}
int main()
{while(cin >> n >> m){memset(tr, 0, sizeof tr);int op, x1, y1, z1, x2, y2, z2;for(int i = 1; i <= m; i++){scanf("%d", &op);if(!op){scanf("%d%d%d", &x1, &y1, &z1);printf("%d\n", sum(x1, y1, z1));}else{scanf("%d%d%d%d%d%d", &x1, &y1, &z1, &x2, &y2, &z2);modify(x1, y1, z1, x2, y2, z2);}}}return 0;
}

长度为 $n(n\le 10^5)$ 的序列，找到有多少个连续区间，满足区间内的最大值减最小值小于 $k$

这种需要枚举所有连续子序列的问题，基本都是暴力枚举一个端点，然后看另一个端点有多少个是满足的. 固定一个端点之后，区间的极差一定是单调的，因此二分就可以了.

其实现在看来只需要双指针就可以了

注意这个题是多组输入，因此求 $st$ 表的时候，要小心不要超过 $n$ 的边界.

#include<bits/stdc++.h>
using namespace std;
const int N = 100010, M = 18;
int lg[N], a[N], n, k;
int Fmax[N][M], Fmin[N][M];
typedef long long ll;
void pre()
{for(int j = 0; j < M; j++){for(int i = 1; i <= n; i++){if(!j) Fmin[i][j] = Fmax[i][j] = a[i];else if(i + (1 << (j - 1)) <= n){Fmax[i][j] = max(Fmax[i][j - 1], Fmax[i + (1 << (j - 1))][j - 1]);Fmin[i][j] = min(Fmin[i][j - 1], Fmin[i + (1 << (j - 1))][j - 1]);}else{Fmax[i][j] = Fmax[i][j - 1], Fmin[i][j] = Fmin[i][j - 1];}}}
}
int query(int l, int r)
{int len = lg[r - l + 1];return max(Fmax[l][len], Fmax[r - (1 << len) + 1][len]) - min(Fmin[l][len], Fmin[r - (1 << len) + 1][len]);
}
int main()
{for(int i = 1; i < N; i++) lg[i] = log2(i);int T;scanf("%d", &T);while(T--){scanf("%d%d", &n, &k);for(int i = 1; i <= n; i++) scanf("%d", &a[i]);pre();ll ans = 0;for(int i = 1; i <= n; i++){int l = 1, r = i;while(r > l){int mid = (l + r) / 2;if(query(mid, i) >= k) l = mid + 1;else r = mid;}ans += (i - l + 1);}printf("%lld\n", ans);}return 0;
}

给你 $n$ 个数，$Q$ 次询问，问你 $(l,r)$ 区间的 $gcd$ 是多少，并且有多少子串的 $gcd$ 和询问的 $gcd$ 是相同的。

$n \le 10^5,Q \le 10^5, a_i \le 10^9 $

任意区间的 $gcd$ 可以用 $st$ 表快速求得。然后我们预处理出每一个 $gcd$ 有多少个。方法是这样的：暴力枚举右端点，那么前面的 $gcd$ 一定是一段一段的. 那么我们可以把前面一段一段的 gcd 存下来，每次加进来一个数，前面会有若干区间的 gcd 下降. 把gcd相同的区间合并成一个区间.

小心答案爆 int.

#include<bits/stdc++.h>
using namespace std;
const int N = 100010, M = 18;
typedef long long ll;
typedef pair<int, int> P;
#define x first
#define y secondint a[N], f[N][M], lg[N];unordered_map<int, ll> mp;
int n, m, kase;
void pre()
{mp.clear();for(int j = 0; j < M; j++){for(int i = 1; (i + (1 << j) - 1) <= n; i++){if(!j) f[i][j] = a[i];else f[i][j] = __gcd(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);}}vector<P> vec;for(int i = 1; i <= n; i++){for(auto& p : vec){p.x = __gcd(p.x, a[i]);}vec.push_back({a[i], 1});vector<P> tmp;for(auto p : vec){if(tmp.size() && tmp.back().x == p.x) tmp.back().y += p.y;else tmp.push_back(p);mp[p.x] += p.y;}vec = tmp;}
}int query(int l, int r)
{int len = lg[r - l + 1];return __gcd(f[l][len], f[r - (1 << len) + 1][len]);
}int main()
{for(int i = 1; i < N; i++) lg[i] = log2(i);int T;scanf("%d", &T);while(T--){scanf("%d\n", &n);for(int i = 1; i <= n; i++){scanf("%d", &a[i]);}pre();printf("Case #%d:\n", ++kase);scanf("%d", &m);for(int i = 1; i <= m; i++){int l, r;scanf("%d%d", &l, &r);int d = query(l, r);printf("%d %lld\n", d, mp[d]);}}return 0;
}

$n(n\le 10^5)$ 个点 $n$ 条无向边的连通图，$Q(Q\le 10^4)$ 个询问，问两点之间的最短路是多少。

基环树，任意删掉一条边，假设是 $(a,b)$. 若询问 $u,v$ 的最小值，则答案在 $dist(u,v),dist(u,a)+w(a,b)+dist(b,v)$ 与 $dist(u,b)+w(a,b)+dist(a,v)$​ 三者取最小值.

无向图基环树，一定要记录from。不然找自环的时候，找的就是无向边的自环.（自行分析）

最近公共祖先还得再写几次，一写一堆bug

#include<bits/stdc++.h>
using namespace std;
const int N = 100010, M = N * 2;
int h[N], e[M], ne[M], w[M], idx;inline void add(int a, int b, int c)
{e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}int n, m;
bool st[N], ins[N];
int rmid, rma, rmb;void dfs_c(int u, int from)
{st[u] = ins[u] = true;for(int i = h[u]; i != -1; i = ne[i]){//无向图基环树，一定要记录from。不然找自环的时候，找的就是无向边的自环.if(i == (from ^ 1)) continue;int v = e[i];if(!st[v]) dfs_c(v, i);else if(ins[v]){rmid = i, rma = u, rmb = v;}}ins[u] = false;
}//小心记录两个depth，一个用作lca的查询，一个用作查询到根节点的距离。因为这个树的边是有权重的.
int fa[N][18], dep[N], ndep[N];void bfs()
{queue<int> que;for(int i = 1; i <= n; i++) ndep[i] = dep[i] = -1;dep[1] = 1, ndep[1] = 0;que.push(1);for(int k = 0; k < 18; k++) fa[1][k] = 1;while(que.size()){int u = que.front(); que.pop();for(int i = h[u]; i != -1; i = ne[i]){if(i == rmid || (i ^ 1) == rmid) continue;int v = e[i];if(dep[v] == -1){dep[v] = dep[u] + 1;ndep[v] = ndep[u] + w[i];fa[v][0] = u;for(int k = 1; k < 18; k++) fa[v][k] = fa[fa[v][k - 1]][k - 1];que.push(v);}}}
}int lca(int a, int b)
{if(dep[a] > dep[b]) swap(a, b);for(int k = 17; k >= 0; k--){if(dep[a] <= dep[fa[b][k]]) b = fa[b][k];}if(a == b) return a;for(int k = 17; k >= 0; k--){if(fa[a][k] != fa[b][k]) a = fa[a][k], b = fa[b][k];}return fa[a][0];
}int dist(int u, int v)
{int anc = lca(u, v);//printf("** u = %d  dep[u] = %d,  v = %d  dep[v] = %d,  anc = %d\n", u, dep[u], v, dep[v], anc);return ndep[u] + ndep[v] - 2 * ndep[anc];
}int main()
{while(cin >> n, n){for(int i = 1; i <= n; i++){h[i] = -1, st[i] = false;}idx = 0;for(int i = 1; i <= n; i++){int a, b, c;scanf("%d%d%d", &a, &b, &c);a++, b++;add(a, b, c), add(b, a, c);}dfs_c(1, -1);bfs();//printf("** remove id = %d, rma = %d, rmb = %d\n", rmid, rma, rmb);scanf("%d", &m);for(int i = 1; i <= m; i++){int u, v;scanf("%d%d", &u, &v);u++, v++;int ans = dist(u, v);ans = min(dist(u, rma) + w[rmid] + dist(rmb, v), ans);ans = min(dist(u, rmb) + w[rmid] + dist(rma, v), ans);printf("%d\n", ans);}}return 0;
}

给出一个长度为 $n$​ 的数组 $A$​，接下来有 $m$​ 次操作

1 l r：对所有区间 $[l,r]$​ 中的整数 $i$​，把 $A[i]$​ 变成 $\phi (A[i])$​ (指欧拉函数)

2 l r x：对所有区间 $[l,r]$​ 中的整数 $i$​，把 $A[i]$​ 变成 $x$​

3 l r：询问 $[l,r]$​ 的区间和

$n,m(n\le 3\times 10^5,m\le 3\times 10^5)$，$1\le A[i]\le 10^7$

保证任何时刻 $1\le A_i\le 10^7$

几个减少代码量的技巧：

1. 由于数组元素任意时刻都保证是正的，因此可以记录一个 $x$​. 如果 $x=0$​，则说明当前区间所有元素并非全部相等。若 $x>0$，则区间所有元素都等于 $x$.
2. 第一个修改操作，若当前区间元素都相等，则可转化为第二个修改操作.

#include<bits/stdc++.h>
#define lson u << 1
#define rson u << 1 | 1typedef unsigned int u32;
typedef int i32;
typedef unsigned long long u64;
typedef long long i64;
typedef __int128_t i128;
typedef __uint128_t u128;using namespace std;
const int N = 300010;const int M = 10000010;
int prime[M], cnt, phi[M];
bool st[M];
void sieve(int n)
{phi[1] = 1;for(int i = 2; i <= n; i++){if(!st[i]) prime[cnt++] = i, phi[i] = i - 1;for(int j = 0; prime[j] * i <= n; j++){st[i * prime[j]] = true;if(i % prime[j] == 0){phi[i * prime[j]] = phi[i] * prime[j];break;}phi[i * prime[j]] = phi[i] * (prime[j] - 1);}}
}struct node
{int l, r, x;bool lazy;u64 sum;
}tr[N * 4];
int a[N];void pushup(int u)
{tr[u].sum = tr[lson].sum + tr[rson].sum;if(tr[lson].x && tr[lson].x == tr[rson].x){tr[u].x = tr[lson].x;}else tr[u].x = 0;
}void build(int u, int l, int r)
{tr[u] = {l, r};if(l == r){tr[u].x = a[l];tr[u].sum = a[l];}else{int mid = l + r >> 1;build(lson, l, mid), build(rson, mid + 1, r);pushup(u);}
}void pushdown(int u)
{if(tr[u].lazy){tr[lson].lazy = tr[rson].lazy = true;tr[lson].x = tr[rson].x = tr[u].x;tr[lson].sum = 1ll * tr[lson].x * (tr[lson].r - tr[lson].l + 1);tr[rson].sum = 1ll * tr[rson].x * (tr[rson].r - tr[rson].l + 1);}tr[u].lazy = false;
}void modify1(int u, int x, int L, int R)
{if(L <= tr[u].l && tr[u].r <= R){tr[u].lazy = true;tr[u].x = x;tr[u].sum = 1ll * x * (tr[u].r - tr[u].l + 1);}else{pushdown(u);int mid = tr[u].l + tr[u].r >> 1;if(L <= mid) modify1(lson, x, L, R);if(R > mid) modify1(rson, x, L, R);pushup(u);}
}void modify2(int u, int L, int R)
{if(L <= tr[u].l && tr[u].r <= R){if(tr[u].x){modify1(u, phi[tr[u].x], L, R);}else{pushdown(u);int mid = tr[u].l + tr[u].r >> 1;modify2(lson, L, R), modify2(rson, L, R);pushup(u);}}else{pushdown(u);int mid = tr[u].l + tr[u].r >> 1;if(L <= mid) modify2(lson, L, R);if(R > mid) modify2(rson, L, R);pushup(u);}
}u64 query(int u, int L, int R)
{if(L <= tr[u].l && tr[u].r <= R){return tr[u].sum;}pushdown(u);int mid = tr[u].l + tr[u].r >> 1;u64 res = 0;if(L <= mid) res += query(lson, L, R);if(R > mid) res += query(rson, L, R);return res;
}int main()
{sieve(M - 1);int T;scanf("%d", &T);while(T--){int n, m;scanf("%d%d", &n, &m);for(int i = 1; i <= n; i++) scanf("%d", &a[i]);build(1, 1, n);for(int i = 1; i <= m; i++){int op, l, r, x;scanf("%d%d%d", &op, &l, &r);if(op == 1){modify2(1, l, r);}else if(op == 2){scanf("%d", &x);modify1(1, x, l, r);}else{printf("%llu\n", query(1, l, r));}}}return 0;
}

第一行一个整数 $n$，代表数列中数的个数。

第二行 $n$ 个正整数，表示初始状态下数列中的数。

第三行一个整数 $m$，表示有 $m$ 次操作。

接下来 $m$ 行每行三个整数 k l r。

• $k=0$ 表示给 [l,r] 中的每个数开平方（下取整）。
• $k=1$ 表示询问 [l,r] 中各个数的和。

数据中有可能 $l>r$，所以遇到这种情况请交换 $l$ 和 $r$。

#include<bits/stdc++.h>#define lson u << 1
#define rson u << 1 | 1typedef unsigned int u32;
typedef int i32;
typedef unsigned long long u64;
typedef long long i64;
typedef __int128_t i128;
typedef __uint128_t u128;const u32 mod = 1e9 + 7;using namespace std;
const int N = 100010;struct node
{int l, r;u64 sum, x;
}tr[N * 4];u64 a[N];void pushup(int u)
{tr[u].sum = tr[lson].sum + tr[rson].sum;if(tr[lson].x && tr[lson].x == tr[rson].x){tr[u].x = tr[lson].x;}else tr[u].x = 0;
}void build(int u, int l, int r)
{tr[u] = {l, r};if(l == r){tr[u].sum = tr[u].x = a[l];}else{int mid = l + r >> 1;build(lson, l, mid), build(rson, mid + 1, r);pushup(u);}
}void modify(int u, int L, int R)
{if(tr[u].l == tr[u].r) tr[u].x = tr[u].sum = sqrt(tr[u].x);else if(L <= tr[u].l && tr[u].r <= R){if(tr[u].x == 1){return;}else{int mid = tr[u].l + tr[u].r >> 1;if(L <= mid) modify(lson, L, R);if(R > mid) modify(rson, L, R);pushup(u);}}else{int mid = tr[u].l + tr[u].r >> 1;if(L <= mid) modify(lson, L, R);if(R > mid) modify(rson, L, R);pushup(u);}
}u64 query(int u, int L, int R)
{if(L <= tr[u].l && tr[u].r <= R){return tr[u].sum;}int mid = tr[u].l + tr[u].r >> 1;u64 res = 0;if(L <= mid) res += query(lson, L, R);if(R > mid) res += query(rson, L, R);return res;
}int main()
{int n;scanf("%d", &n);for(int i = 1; i <= n; i++){scanf("%llu", &a[i]);}build(1, 1, n);int m;scanf("%d", &m);for(int i = 1; i <= m; i++){int k, l, r;scanf("%d%d%d", &k, &l, &r);if(l > r) swap(l, r);if(k == 0){modify(1, l, r);}else{printf("%llu\n", query(1, l, r));}}return 0;
}

用懒标记维护的版本。minlen 表示当前区间涵盖所有区间，$cnt$​ 最小的时候区间长度之和.

这样子，维护的其实是覆盖 $0$ 次的区间长度之和. 最后总长度减去它就可以了.

#include<bits/stdc++.h>
#define x first
#define y second
#define lowbit(x) ((x) & (-x))
#define all(x) x.begin(), x.end()
#define pcount  __builtin_popcount
#define lcount  __builtin_clz
#define rcount  __builtin_ctz
#define qcin std::ios::sync_with_stdio(false); std::cin.tie(nullptr);
#define tempt template<class T>
#define lson u << 1
#define rson u << 1 | 1typedef unsigned int u32;
typedef int i32;
typedef unsigned long long u64;
typedef long long i64;using namespace std;
const int N = 10010;struct node
{int l, r, mincnt;int lazy;double minlen, len;
}tr[N * 8];struct seg
{double x, y1, y2;int t;bool operator < (const seg& s) const{return x < s.x;}
}segs[N * 2];vector<double> ys;int find(double x)
{return lower_bound(ys.begin(), ys.end(), x) - ys.begin();
}void pushup(int u)
{tr[u].mincnt = min(tr[lson].mincnt, tr[rson].mincnt);double minlen = 0;if(tr[u].mincnt == tr[lson].mincnt) minlen += tr[lson].minlen;if(tr[u].mincnt == tr[rson].mincnt) minlen += tr[rson].minlen;tr[u].minlen = minlen;
}void pushdown(int u)
{tr[lson].mincnt += tr[u].lazy, tr[rson].mincnt += tr[u].lazy;tr[lson].lazy += tr[u].lazy, tr[rson].lazy += tr[u].lazy;tr[u].lazy = 0;
}void build(int u, int l, int r)
{double len = ys[r + 1] - ys[l];tr[u] = {l, r, 0, 0, len, len};if(l == r) return;else{int mid = l + r >> 1;build(lson, l, mid), build(rson, mid + 1, r);}
}void modify(int u, int L, int R, int t)
{if(L <= tr[u].l && tr[u].r <= R){tr[u].mincnt += t;tr[u].lazy += t;}else{pushdown(u);int mid = tr[u].l + tr[u].r >> 1;if(L <= mid) modify(lson, L, R, t);if(R > mid) modify(rson, L, R, t);pushup(u);}
}int kase;
int main()
{int n;while(cin >> n, n){int sz = 0;ys.clear();for(int i = 1; i <= n; i++){double x1, y1, x2, y2;scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);segs[sz++] = {x1, y1, y2, 1};segs[sz++] = {x2, y1, y2, -1};ys.push_back(y1), ys.push_back(y2);}sort(ys.begin(), ys.end());ys.erase(unique(ys.begin(), ys.end()), ys.end());sort(segs, segs + 2 * n);build(1, 0, ys.size() - 2);double ans = 0;for(int i = 0; i < 2 * n; i++){if(i){double len = tr[1].len;if(!tr[1].mincnt) len -= tr[1].minlen;ans += len * (segs[i].x - segs[i - 1].x);}modify(1, find(segs[i].y1), find(segs[i].y2) - 1, segs[i].t);//printf("%f %d %f\n", tr[1].len, tr[1].mincnt, tr[1].minlen);}printf("Test case #%d\nTotal explored area: %.2f\n\n", ++kase, ans);}return 0;
}

三种操作：
1 a b c，在建立权值为 $c$​ 的 $a\to b$​ 的单向边
2 a b c d，建立 $a\to [b,c]$​ 权值为 $d$​ 的单向边
3 a b c d，建立 $[b,c]\to a$​ 权值为 $d$​​ 的单向边

给你一个起点，问你起点到其他点的最短路长度

$1\le n,q\le 10^5$

借助线段树建立为每个区间建立一个结点，有一个需要注意的问题，为了保证某个点可以走到它对应的所有区间，并且它所有对应的区间能走到它，并且不能形成长度为 $0$ 的环。因此可以建立两棵线段树，一棵从父结点向子结点连长度为 $0$ 的边，一棵从子结点向父结点连长度为 $0$ 的边. 子结点之间相互连长度为 $0$ 的边.

当然我们不用真的建立两棵线段树，只需要把对应的线段树编号找到就可以了. 第一个线段树的编号加 $4n$ 就是第二棵线段树的编号.

#include<bits/stdc++.h>
#define x first
#define y second
typedef long long ll;using namespace std;
const int N = 100010, M = 6000010;
const ll INF = 0x3f3f3f3f3f3f3f3fll;struct node
{int l, r;
}tr[N * 4];int h[N * 8], e[M], ne[M], id[N], idx;
ll w[M], d[N * 8];int n, q, s;
typedef pair<ll, int> P;
bool st[N * 8];void add(int a, int b, ll c)
{e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}void build(int u, int l, int r)
{tr[u] = {l, r};if(l == r){id[l] = u;add(u, u + 4 * n, 0), add(u + 4 * n, u, 0);}else{int mid = l + r >> 1;build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);add(u, u << 1, 0), add(u, u << 1 | 1, 0);add((u << 1) + 4 * n, u + 4 * n, 0), add((u << 1 | 1) + 4 * n, u + 4 * n, 0);}
}void modify(int u, int l, int r, int x, ll c, int op)
{if(l <= tr[u].l && tr[u].r <= r){if(op == 2) add(x, u, c), add(x + 4 * n, u + 4 * n, c);else add(u, x, c), add(u + 4 * n, x + 4 * n, c);}else{int mid = tr[u].l + tr[u].r >> 1;if(l <= mid) modify(u << 1, l, r, x, c, op);if(r > mid) modify(u << 1 | 1, l, r, x, c, op);}
}void dijkstra()
{memset(d, 0x3f, sizeof d);d[id[s]] = 0;priority_queue<P, vector<P>, greater<P>> que;que.push({0, id[s]});while(que.size()){int u = que.top().y; que.pop();if(st[u]) continue;st[u] = true;for(int i = h[u]; i != -1; i = ne[i]){int v = e[i];if(d[v] > d[u] + w[i]){d[v] = d[u] + w[i];que.push({d[v], v});}}}
}
int main()
{memset(h, -1, sizeof h);scanf("%d%d%d", &n, &q, &s);build(1, 1, n);for(int i = 1; i <= q; i++){int op, a, b, c, d;scanf("%d%d%d%d", &op, &a, &b, &c);if(op == 1){//注意是 id[a] 而不是 aadd(id[a], id[b], c);add(id[a] + 4 * n, id[b] + 4 * n, c);}else if(op == 2){scanf("%d", &d);//注意是 id[a] 而不是 amodify(1, b, c, id[a], d, 2);}else{scanf("%d", &d);//注意是 id[a] 而不是 amodify(1, b, c, id[a], d, 3);}}dijkstra();for(int i = 1; i <= n; i++){//注意是 d[id[i]] 不是 d[i]printf("%lld%c", d[id[i]] == INF ? -1LL : d[id[i]], i == n ? '\n' : ' ');}return 0;
}

题意：给定一棵树。询问 $s,t$ 之间路径上的点权和，点权在 $[a,b]$​ 内才有效，否则该点权为 $0$

从每个节点向父结点建立可持久化权值线段树，查询的时候就是 $root[s]+root[t]-root[lca(s,t)]-root[fa[lca(s,t)]]$.

终于调出来了

第一个错误：主席树由于维护的是权值，查询的是点权之和。因此从子结点向父结点建立版本的时候，要 tr[p].sum += nums[x]，不是 tr[p].sum = nums[x]

第二个错误：注意找 $[a,b]$ 区间的时候，一个是找 $\ge a$ 的最小值，一个是找 $\le b$ 的最大值，不能全用 lower_bound 处理.

#include<bits/stdc++.h>
using namespace std;
const int N = 100010, M = N * 2;
typedef long long ll;
int h[N], e[M], ne[M], idx;
ll w[N];int fa[N][18];
int n, m;void add(int a, int b)
{e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}int q[N], dep[N];
void bfs()
{memset(dep, -1, sizeof dep);dep[0] = 0, dep[1] = 1;int hh = 0, tt = -1;q[++tt] = 1;while(hh <= tt){int u = q[hh++];for(int i = h[u]; i != -1; i = ne[i]){int v = e[i];if(dep[v] != -1) continue;dep[v] = dep[u] + 1;fa[v][0] = u;for(int j = 1; j < 18; j++) fa[v][j] = fa[fa[v][j - 1]][j - 1];q[++tt] = v;}}
}int lca(int a, int b)
{if(dep[a] < dep[b]) swap(a, b);for(int k = 17; k >= 0; k--){if(dep[fa[a][k]] >= dep[b]){a = fa[a][k];}}if(a == b) return a;for(int k = 17; k >= 0; k--){if(fa[a][k] != fa[b][k]){a = fa[a][k], b = fa[b][k];}}return fa[a][0];
}struct node
{int l, r;ll sum;
}tr[N * 4 + N * 17];int cnt;
vector<ll> nums;
int root[N];
int find(ll x)
{return lower_bound(nums.begin(), nums.end(), x) - nums.begin();
}
void pushup(int u)
{tr[u].sum = tr[tr[u].l].sum + tr[tr[u].r].sum;
}int build(int l, int r)
{int p = ++cnt;if(l == r){tr[p] = {l, r, 0};return p;}int mid = l + r >> 1;tr[p].l = build(l, mid), tr[p].r = build(mid + 1, r);pushup(p);return p;
}int insert(int p, int l, int r, int x)
{int q = ++cnt;tr[q] = tr[p];if(l == r){tr[q].sum += nums[x];return q;}int mid = l + r >> 1;if(x <= mid) tr[q].l = insert(tr[p].l, l, mid, x);else tr[q].r = insert(tr[p].r, mid + 1, r, x);pushup(q);return q;
}ll query(int s, int t, int anc, int anc_fa, int l, int r, int L, int R)
{if(L <= l && r <= R) return tr[s].sum + tr[t].sum - tr[anc].sum - tr[anc_fa].sum;int mid = l + r >> 1;ll res = 0;if(L <= mid) res += query(tr[s].l, tr[t].l, tr[anc].l, tr[anc_fa].l, l, mid, L, R);if(R > mid) res += query(tr[s].r, tr[t].r, tr[anc].r, tr[anc_fa].r, mid + 1, r, L, R);return res;
}void dfs(int u, int fa)
{root[u] = insert(root[fa], 0, nums.size() - 1, find(w[u]));for(int i = h[u]; i != -1; i = ne[i]){int v = e[i];if(v == fa) continue;dfs(v, u);}
}int main()
{while(cin >> n >> m){memset(h, -1, sizeof h);idx = 0, cnt = 0;nums.clear();for(int i = 1; i <= n; i++){scanf("%lld", &w[i]);nums.push_back(w[i]);}sort(nums.begin(), nums.end());nums.erase(unique(nums.begin(), nums.end()), nums.end());for(int i = 1; i < n; i++){int a, b;scanf("%d%d", &a, &b);add(a, b), add(b, a);}bfs();root[0] = build(0, nums.size() - 1);dfs(1, 0);for(int i = 1; i <= m; i++){int s, t;ll a, b;scanf("%d%d%lld%lld", &s, &t, &a, &b);int anc = lca(s, t);int anc_fa = fa[anc][0];a = find(a), b = upper_bound(nums.begin(), nums.end(), b) - nums.begin() - 1;ll ans = query(root[s], root[t], root[anc], root[anc_fa], 0, nums.size() - 1, a, b);printf("%lld%c", ans, i == m ? '\n' : ' ');}}return 0;
}

题意：给定一颗有 $n$ 个叶节点的二叉树。每个叶节点都有一个权值 $p_i$（注意，根不是叶节点），所有叶节点的权值构成了一个 $1\sim n$ 的排列。对于这棵二叉树的任何一个结点，保证其要么是叶节点，要么左右两个孩子都存在。现在你可以任选一些节点，交换这些节点的左右子树。在最终的树上，按照先序遍历遍历整棵树并依次写下遇到的叶结点的权值构成一个长度为 $n$ 的排列，你需要最小化这个排列的逆序对数。输出这个逆序对数。

线段树合并裸题，每个叶节点建立权值线段树，看看交换与不交换对答案的贡献分别是多少

我们要求的是逆序对最小，对于一个节点，逆序对有三种：

• 在左子树中。
• 在右子树中。
• 跨越了左右子树。

我们清楚，交换子树只会对第三种情况产生影响。因此，我们只需要在合并线段树的过程中统计交换子树的逆序对个数 $u$ 和不交换子树的逆序对个数 $v$，取 $min(u,v)$ 累加到答案中就行了。

现在的问题是如何找第三种情况下的逆序对。

很明显，对于除了叶节点的每一个节点：

1. 如果不交换： $u+=[p.rs].size\ast [q.ls].size$
2. 如果交换： $v+=[p.ls].size\ast [q.rs].size$

重点：每一次合并线段树时，递归到除了叶节点的所有节点，都要累加逆序对个数 u,v。

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
typedef long long ll;
struct node
{int l, r, sz;
}tr[N * 50];
int n, idx;
ll res1, res2, ans;int modify(int l, int r, int x)
{int q = ++idx;tr[q].sz = 1;if(l == r) return q;int mid = l + r >> 1;if(x <= mid) tr[q].l = modify(l, mid, x);else tr[q].r = modify(mid + 1, r, x);return q;
}int merge(int p, int q, int l, int r)
{if(!p || !q) return p ? p : q;if(l == r){tr[p].sz += tr[q].sz;return p;}else{res1 += 1ll * tr[tr[p].r].sz * tr[tr[q].l].sz;res2 += 1ll * tr[tr[p].l].sz * tr[tr[q].r].sz;int mid = l + r >> 1;tr[p].l = merge(tr[p].l, tr[q].l, l, mid);tr[p].r = merge(tr[p].r, tr[q].r, mid + 1, r);tr[p].sz = tr[tr[p].l].sz + tr[tr[p].r].sz;return p;}
}int dfs()
{int x;scanf("%d", &x);if(!x){int l = dfs(), r = dfs();res1 = res2 = 0;int p = merge(l, r, 1, n);ans += min(res1, res2);return p;}else{int p = modify(1, n, x);return p;}
}int main()
{scanf("%d", &n);dfs();printf("%lld\n", ans);
}

• 给一个长度为 $n(n\le 5\ast 10^4)$ 的序列，一开始都是 $0$，有 $q$ 种操作：找到一段长度为 $k$ 的全为 $0$ 的子串，使开始位置尽可能得小，输出起始位置，然后把这段全部变成1，找不到的话输出 $0$；使得一段区间全部变成 $0$.

每个点维护左起一段连续最长的空住房，以及右起一段连续的最长的空住房，在表示的区间内最长的连续空住房数。

如何合并信息？

前两个很好维护，但是要特判一边全部都是空住房的时候。

最后一个也好维护，首先用两边原来的答案来更新。把两个区间拼接起来会导致中间的连续一段空住房变长，所以还需要用它来更新答案。

对于lazy标记的下放，因为是覆盖，所以直接改就好了。

这道题的WA了很久才过 懒标记之间会有相互限制，就比如这个题，lazy0 和 lazy1 一定不会同时为1，因此一旦修改其中一个是1，另一个必须要修改为0.

当然这道题的懒标记开一个就行了，因为他们是相互限制的嘛.

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 50010;
struct node
{int l, r;int lmax, rmax, mmax;int lazy;
}tr[N * 4];
int n, m;
void pushup(int u)
{if(tr[u << 1].mmax == tr[u << 1].r - tr[u << 1].l + 1){tr[u].lmax = tr[u << 1].mmax + tr[u << 1 | 1].lmax;}else tr[u].lmax = tr[u << 1].lmax;if(tr[u << 1 | 1].mmax == tr[u << 1 | 1].r - tr[u << 1 | 1].l + 1){tr[u].rmax = tr[u << 1].rmax + tr[u << 1 | 1].mmax;}else tr[u].rmax = tr[u << 1 | 1].rmax;tr[u].mmax = max(max(tr[u << 1].mmax, tr[u << 1 | 1].mmax), tr[u << 1].rmax + tr[u << 1 | 1].lmax);
}void pushdown(int u)
{if(tr[u].lazy != -1){tr[u << 1].lmax = tr[u << 1].rmax = tr[u << 1].mmax = (tr[u << 1].r - tr[u << 1].l + 1) * (tr[u].lazy ^ 1);tr[u << 1 | 1].lmax = tr[u << 1 | 1].rmax = tr[u << 1 | 1].mmax = (tr[u << 1 | 1].r - tr[u << 1 | 1].l + 1) * (tr[u].lazy ^ 1);tr[u << 1].lazy = tr[u << 1 | 1].lazy = tr[u].lazy;}tr[u].lazy = -1;
}void build(int u, int l, int r)
{tr[u].l = l,  tr[u].r = r;if(l == r){tr[u].lmax = tr[u].rmax = tr[u].mmax = 1;tr[u].lazy = -1;}else{int mid = l + r >> 1;build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);pushup(u);}
}
void modify(int u, int l, int r, int x)
{if(l <= tr[u].l && tr[u].r <= r){tr[u].lazy = x;tr[u].lmax = tr[u].rmax = tr[u].mmax = (tr[u].r - tr[u].l + 1) * (x ^ 1);}else{pushdown(u);int mid = tr[u].l + tr[u].r >> 1;if(l <= mid) modify(u << 1, l, r, x);if(r > mid) modify(u << 1 | 1, l, r, x);pushup(u);}
}
int query(int u, int k)
{if(tr[u].mmax < k) return 0;if(tr[u].l == tr[u].r) return tr[u].l;pushdown(u);if(tr[u << 1].mmax >= k) return query(u << 1, k);if(tr[u << 1].rmax + tr[u << 1 | 1].lmax >= k) return tr[u << 1].r - tr[u << 1].rmax + 1;else return query(u << 1 | 1, k);
}int main()
{scanf("%d%d", &n, &m);build(1, 1, n);for(int i = 1; i <= m; i++){int op, l, k;scanf("%d", &op);if(op == 1){scanf("%d", &k);int res = query(1, k);printf("%d\n", res);if(res) modify(1, res, res + k - 1, 1);}else{scanf("%d%d", &l, &k);modify(1, l, l + k - 1, 0);}}return 0;
}

如题，你需要维护这样的一个长度为 NN 的数组，支持如下几种操作

1. 在某个历史版本上修改某一个位置上的值
2. 访问某个历史版本上的某一位置的值

此外，每进行一次操作（对于操作2，即为生成一个完全一样的版本，不作任何改动），就会生成一个新的版本。版本编号即为当前操作的编号（从1开始编号，版本0表示初始状态数组）

简单的可持久化线段树，不需要建立权值线段树

注意数组千万别开小，因为询问是 $10^6$ 次.

#include<bits/stdc++.h>
using namespace std;
const int N = 1000010;
struct node
{int l, r, value;
}tr[N * 4 + N * 20];
//小心询问次数达到1e6，数组千万别开小.
int n, m, a[N], root[N], idx;int build(int l, int r)
{int q = ++idx;if(l == r){tr[q].value = a[l];return q;}int mid = l + r >> 1;tr[q].l = build(l, mid), tr[q].r = build(mid + 1, r);return q;
}int modify(int p, int l, int r, int x, int v)
{int q = ++idx;tr[q] = tr[p];if(l == r){tr[q].value = v;return q;}int mid = l + r >> 1;if(x <= mid) tr[q].l = modify(tr[p].l, l, mid, x, v);else tr[q].r = modify(tr[p].r, mid + 1, r, x, v);return q;
}int query(int p, int l, int r, int x, int& res)
{int q = ++idx;tr[q] = tr[p];if(l == r){res = tr[q].value;return q;}int mid = l + r >> 1;if(x <= mid) tr[q].l = query(tr[p].l, l, mid, x, res);else tr[q].r = query(tr[p].r, mid + 1, r, x, res);return q;
}int main()
{scanf("%d%d", &n, &m);for(int i = 1; i <= n; i++) scanf("%d", &a[i]);root[0] = build(1, n);for(int i = 1; i <= m; i++){int v, op, loc, value;scanf("%d%d%d", &v, &op, &loc);if(op == 1){scanf("%d", &value);root[i] = modify(root[v], 1, n, loc, value);}else{int res;root[i] = query(root[v], 1, n, loc, res);printf("%d\n", res);}}return 0;
}