T1 Bubble Sort 2
题意：给定一个长度为 \(n\) 的序列 \(a\)，进行 \(q\) 次修改，第 \(i\) 次将第 \(x_i\) 个元素的值修改为 \(y_i\)。
对于每次操作后，你都需要求出，如果此时对序列进行冒泡排序，需要多少次冒泡才能完成排序。
\(n \le 5 \times 10^5\)。
序列有序意味着，每个数前面都没有大于自身的数。假设一个元素 \(i\) 前面有 \(c_i\) 个数大于自身，考虑进行一次冒泡后 \(c_i\) 个元素中最大的会到 \(i\) 后面，其他的还是在 \(i\) 前面。相当于一次冒泡是 \(\forall c_i > 0, c_i \gets c_i - 1\)。所以答案显然为
对于这个直接树套树维护动态二维偏序，时间复杂度 \(O(n \log^2 n)\)。无法通过。
考虑对于一个 \(i\)，若存在 \(k > i\) 使得 \(a_k < a_i\)，那么 \(k\) 相对于 \(i\) 不劣，此时我们可以不计算 \(i\) 的贡献。也就是说，计算答案时只需考虑所有后缀最小值。
那么我们考虑对限制放缩，对于一个数 \(i\)，我们直接钦定 \(i\) 后面的数全部大于 \(i\)，此时对于后缀 \(\min\) 的位置答案不变，对于非后缀 \(\min\) 的位置答案变小了，所以这样做是对的、那么我们要计算的就是：
这个东西考虑用权值线段树维护，一个数修改时的影响就是一段前缀加或减，这个都好维护。
时间复杂度 \(O(n \log n)\)。
Code
#include "bubblesort2.h"
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>#define lc (k << 1)
#define rc ((k << 1) | 1)using namespace std;const int N = 5e5 + 5, T = N * 8;
const int Inf = 1e9;int n, q, m;
int a[N], p[N * 2], tx[N], ty[N];
set<int> s[N * 2];
int mx[T], tag[T];void Modify (int k, int x, int y, int L = 1, int R = m) {if (L == R) {mx[k] = y + tag[k];return;}int mid = (L + R) >> 1;if (x <= mid) {Modify(lc, x, y, L, mid);}else {Modify(rc, x, y, mid + 1, R);}mx[k] = max(mx[lc], mx[rc]) + tag[k];
}void Add (int k, int l, int r, int x, int L = 1, int R = m) {if (l <= L && r >= R) {tag[k] += x, mx[k] += x;return;} int mid = (L + R) >> 1;if (l <= mid) {Add(lc, l, r, x, L, mid);}if (r > mid) {Add(rc, l, r, x, mid + 1, R);}mx[k] = max(mx[lc], mx[rc]) + tag[k];
}void Insert_val (int x, int v) {s[v].insert(x);Modify(1, v, *--s[v].end() - n);if (v > 1)Add(1, 1, v - 1, 1);
} void Remove_val (int x, int v) {s[v].erase(x);Modify(1, v, s[v].empty() ? -Inf : *--s[v].end() - n);if (v > 1) Add(1, 1, v - 1, -1);
}vector<int> countScans (vector<int> A, vector<int> X, vector<int> V) {q = X.size();for (auto i : A) {a[++n] = i, p[++m] = i; }for (auto &i : X) ++i;for (auto i : V) {p[++m] = i;}sort(p + 1, p + m + 1);m = unique(p + 1, p + m + 1) - p - 1; for (int i = 1; i <= n; ++i) {a[i] = lower_bound(p + 1, p + m + 1, a[i]) - p; }for (auto &i : V) {i = lower_bound(p + 1, p + m + 1, i) - p; }fill(mx, mx + m * 4 + 1, -Inf);for (int i = 1; i <= n; ++i) {Insert_val(i, a[i]);} vector<int> ans;for (int i = 0; i < q; ++i) {int x = X[i], y = V[i];Remove_val(x, a[x]);Insert_val(x, a[x] = y);ans.push_back(mx[1]);}return ans;
}
T2 Cats or Dogs
花园中有 \(n\) 个小屋，这些小屋通过 \(n - 1\) 条边相连，构成一棵树。每个小屋有三种状态：有一只猫，有一只狗，或者什么都没有。
定义当前时刻花园的危险级别为，最少要切断树上的多少条边，使得任意一对猫和狗无法互相到达。
进行 \(q\) 次操作，每次操作形如将一个没有宠物的小屋放一猫或狗，或者将某个小屋内的猫或狗移除，然后求花园的危险级别。
\(1 \le n, q \le 10^5\)。
考虑一个平凡的暴力：设 \(f_{i, 0}\) 表示使得 \(i\) 子树内与 \(i\) 连接的连通块中没有猫的最小代价，\(f_{i, 1}\) 类似的表示没有狗的最小代价。时间复杂度 \(O(nq)\)。
然后我们用动态树分治优化。设 \(g_{i, 0}\) 表示 \(i\) 的所有轻子树内没有猫的最小代价，\(g_{i, 1}\) 表示 \(i\) 的所有轻子数内没有狗的最小代价。注意在这里我们允许花 \(1\) 的代价切断 \(i \rightarrow son_i\) 的边。
考虑一个结点 \(u\)，我们求出了 \(g_u\) 和其重儿子的 \(f\)，则 \(f_u\) 的转移方程
其中 \(a_u = 1\) 表示 \(u\) 结点处为猫，\(a_u = 2\) 表示 \(u\) 结点处为狗。我们将转移写成 \((\min, +)\) 矩阵乘法的形式：
剩下的就是动态树分治板子了，对于重链线段树维护转移矩阵，对于轻边暴力跳即可。
时间复杂度 \(O(n \log^2 n)\)。
Code
#include <iostream>
#include <vector>
#include <array>
#include "catdog.h"using namespace std;
using Vec = array<int, 2>;const int N = 1e5 + 5;
const Vec Evec = {0, 0};int n, a[N];
vector<int> e[N];
int fa[N], siz[N], dep[N], wson[N];
int dfn[N], rmp[N], now, tp[N], bot[N];
int f[N][2], g[N][2];void Dfs (int u) {siz[u] = 1;dep[u] = dep[fa[u]] + 1;for (auto v : e[u]) {if (v != fa[u]) {fa[v] = u, Dfs(v);siz[u] += siz[v];if (siz[v] > siz[wson[u]]) {wson[u] = v;}}}
}void Dfs2 (int u, int t) {dfn[u] = ++now;rmp[now] = u; tp[u] = t, bot[t] = u; if (wson[u]) {Dfs2(wson[u], t);}for (auto v : e[u]) {if (v != fa[u] && v != wson[u]) {Dfs2(v, v);}}
}struct Mat {array<Vec, 2> a;Vec& operator[] (int x) {return a[x];}Mat () { a[0][0] = a[0][1] = a[1][0] = a[1][1] = 0; }Mat (int p, int q, int r, int s) {a[0][0] = p, a[0][1] = q, a[1][0] = r, a[1][1] = s;}Mat operator* (Mat b) {Mat res(N, N, N, N);for (int i = 0; i < 2; ++i) {for (int j = 0; j < 2; ++j) {for (int k = 0; k < 2; ++k) {res[i][j] = min(res[i][j], a[i][k] + b[k][j]);}}}return res;}Vec operator* (Vec b) {Vec res = {N, N};for (int i = 0; i < 2; ++i) {for (int j = 0; j < 2; ++j) {res[i] = min(res[i], a[i][j] + b[j]);}}return res;}
} mat[N];namespace Seg {#define lc (k << 1)#define rc ((k << 1) | 1)const int T = N * 4;Mat tr[T];void Pushup (int k) {tr[k] = tr[lc] * tr[rc];}void Update (int k, int x, Mat a, int L = 1, int R = n) {if (L == R) { tr[k] = a;return;}int mid = (L + R) >> 1;if (x <= mid) {Update(lc, x, a, L, mid);}else {Update(rc, x, a, mid + 1, R);}Pushup(k);}Mat Query (int k, int l, int r, int L = 1, int R = n) {if (l <= L && r >= R) {return tr[k];}int mid = (L + R) >> 1;if (l > mid) { return Query(rc, l, r, mid + 1, R);} else if (r <= mid) {return Query(lc, l, r, L, mid);}else { return Query(lc, l, r, L, mid) * Query(rc, l, r, mid + 1, R);}}#undef lc #undef rc
}void Calc (int u) {Mat ret = Seg::Query(1, dfn[u], dfn[bot[u]]);Vec rev = ret * Evec;f[u][0] = rev[0], f[u][1] = rev[1];
} void Build_mat (int u) {int d0 = (a[u] == 1 ? N : 0), d1 = (a[u] == 2 ? N : 0);mat[u] = Mat(g[u][0] + d0, g[u][0] + 1 + d0, g[u][1] + 1 + d1, g[u][1] + d1);Seg::Update(1, dfn[u], mat[u]);
}void DP (int u) {for (auto v : e[u]) {if (v != fa[u] && v != wson[u]) {DP(v);g[u][0] += min(f[v][0], f[v][1] + 1);g[u][1] += min(f[v][1], f[v][0] + 1);}}if (wson[u]) { DP(wson[u]);}Build_mat(u);if (tp[u] == u) {Calc(u);}
}void Update_path (int u) {while (u) {Build_mat(u);int v = tp[u], tf[2] = {f[v][0], f[v][1]};Calc(v);u = fa[v];if (u) {g[u][0] += min(f[v][0], f[v][1] + 1) - min(tf[0], tf[1] + 1);g[u][1] += min(f[v][1], f[v][0] + 1) - min(tf[1], tf[0] + 1);}}
}void initialize (int N, vector<int> A, vector<int> B) {n = N;for (int i = 0; i < n; ++i) {e[A[i]].push_back(B[i]);e[B[i]].push_back(A[i]);}Dfs(1), Dfs2(1, 1), DP(1);
}int Get_ans () {return min(f[1][0], f[1][1]);
}int cat (int v) {a[v] = 1, Update_path(v);return Get_ans();
}int dog (int v) {a[v] = 2, Update_path(v);return Get_ans();
}int neighbor (int v) {a[v] = 0, Update_path(v);return Get_ans();
}// void Test () {
// freopen("02-02.in", "r", stdin);
// freopen("02-02.out", "w", stdout);
// int N;
// cin >> N;
// vector<int> A(N), B(N);
// for (int i = 0; i < N - 1; ++i) {
// cin >> A[i] >> B[i];
// }
// initialize(N, A, B);
// int Q;
// cin >> Q;
// for (int T, v; Q--; ) {
// cin >> T >> v;
// cout << (T == 1 ? cat : (T == 2 ? dog : neighbor))(v) << '\n';
// }
// }// int main () { Test(); }
T3 Collapse
有 \(n\) 座城镇，一段电缆可以双向连接两个城镇 \(u\) 和 \(v\)，接下来的 \(m\) 天中每一天恰好会建设或拆除一段电缆。
这些城镇之间经常发生山体滑坡，若城镇 \(x\) 和 \(x + 1\) 发生山体滑坡，则对于形如 \((u, v)\) 的电缆（不妨设 \(u < v\)），若 \(u \le x\) 且 \(v \ge x + 1\) 则该电缆不可用。
此时需要建立一些基站，你需要使得每个城镇都可以通过若干电缆和一个基站连接。
现在给出 \(q\) 次询问，每次询问给出 \(t, x\)，你需要求出若在第 \(t\) 天时城镇 \(x\) 和 \(x + 1\) 发生山体滑坡，最少要建立多少个基站、
\(1 \le n, q \le 10^5\)。
首先重新描述题意：每条边 \((u, v)\) 有出现时间 \([l, r]\)，每次询问在时间 \(t\)，如果只保留 \([1, x]\) 和 \([x + 1, n]\) 内部的边，有多少连通块。
显然 \([1, x]\) 和 \([x + 1, n]\) 两个部分可以分别计算连通块数再相加，并且两部分是对偶的，所以我们下面只考虑计算 \([1, x]\)。
我们对所有询问按 \(t\) 排序，再对每 \(B\) 个询问分一个块，考虑对于每个块如何算答案。
考察每条边对这些询问的贡献，设这条边的出现时间为 \([l, r]\)，块内询问的时间段为 \([L, R]\)。
若 \([l, r]\) 包含 \([L, R]\)，则这条边对整个块都有贡献，我们将所有这样的边按 \(y\) 排序，块内的询问按 \(x\) 排序，扫描线即可。时间复杂度 \(O(\frac{qm}{B} \log n)\)。
若 \([l, r]\) 不包含但与 \([L, R]\)，那么对于每条边只会落入这种情况 \(O(1)\) 次，此时我们在遇到一个询问时暴力加入这一类型的边，然后在撤销回去即可，并查集需要按秩合并。时间复杂度 \(O(mB \log n)\)。
总时间复杂度 \(O((\frac{qm}{B} + mB) \log n)\)，代码中取 \(B = 333\)（随便取的，没仔细卡）。由于并查集和排序的 \(\log\) 常数很小，并且这题的加边方式很难卡满，可以通过。
Code
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <numeric>
#include <algorithm>
#include "collapse.h"using namespace std;
using Pii = pair<int, int>; const int N = 1e5 + 5, B = 333;int n, m, q;
int fa[N], p[N];
set<Pii> es;
map<Pii, int> mp;struct E {int x, y, l, r;// One edge connected x and y with time [l, r]
}; struct Q {int t, p, id;
}; struct Union_find {int fa[N], d[N]; vector<Pii> v; void Init () {iota(fa + 1, fa + n + 1, 1);fill(d + 1, d + n + 1, 0);v.clear();}int Find (int x) {return fa[x] == x ? x : Find(fa[x]);} void Unite (int x, int y) {x = Find(x), y = Find(y);if (d[x] < d[y]) swap(x, y);v.push_back({y, d[x]});fa[y] = x; d[x] = max(d[x], d[y] + 1);}bool Try_to_unite (int x, int y) {x = Find(x), y = Find(y);if (x == y) return 0; Unite(x, y); return 1;}int Get_time () {return v.size();}void Roll_back (int t) {while (v.size() > t) {Pii t = v.back();v.pop_back();d[fa[t.first]] = t.second;fa[t.first] = t.first;}}
} uf;vector<E> ev; int Find (int x) {if (fa[x] == x) return x;return fa[x] = Find(fa[x]);
} vector<int> simulateCollapse (int N, vector<int> T, vector<int> X, vector<int> Y, vector<int> W, vector<int> P) {[&]() -> void {// Remaken = N, m = T.size(), q = W.size();for (auto &x : X) ++x;for (auto &y : Y) ++y; for (auto &w : W) ++w;for (auto &p : P) ++p;for (int i = 0; i < m; ++i) {if (X[i] > Y[i]) swap(X[i], Y[i]);}for (int i = 0; i < m; ++i) {int x = X[i], y = Y[i];if (!T[i]) {mp.insert({{x, y}, i + 1});}else {auto it = mp.find({x, y});ev.push_back(E({x, y, it->second, i}));mp.erase(it);}}for (auto i : mp) {ev.push_back(E({i.first.first, i.first.second, i.second, m})); }// cout << "Edge set : " << '\n';// for (auto i : ev) {// cout << i.x << ' ' << i.y << ' ' << i.l << ' ' << i.r << '\n';// }// cout << "-------------" << '\n';// exit(0);}();iota(p, p + q, 0);sort(p, p + q, [&](int i, int j) -> bool {return W[i] < W[j];});vector<int> ans(q);for (int tl = 0, tr; tl < q; tl = tr + 1) {tr = min(tl + B - 1, q - 1);int L = W[p[tl]], R = W[p[tr]];vector<Pii> cover;vector<E> vec; for (auto e : ev) {if (e.l <= L && e.r >= R) {cover.push_back({e.x, e.y});}else if (R >= e.l && e.r >= L) {vec.push_back(e);}}sort(cover.begin(), cover.end(), [&](Pii a, Pii b) -> bool {return a.second < b.second;});vector<Q> qv;for (int i = tl; i <= tr; ++i) {int id = p[i];qv.push_back(Q({W[id], P[id], id}));}sort(qv.begin(), qv.end(), [&](Q a, Q b) -> bool {return a.p < b.p;});auto cur = cover.begin();uf.Init();int ucnt = 0;// The times of successful mergefor (auto q : qv) {int p = q.p, t = q.t, id = q.id;while (cur != cover.end() && cur->second <= p) {ucnt += uf.Try_to_unite(cur->first, cur->second);++cur;}int timel = uf.Get_time(), tmpcnt = 0; for (auto e : vec) {if (e.l <= t && e.r >= t && e.y <= p) {tmpcnt += uf.Try_to_unite(e.x, e.y);}}ans[q.id] += p - ucnt - tmpcnt;uf.Roll_back(timel);}reverse(qv.begin(), qv.end());sort(cover.begin(), cover.end(), [&](Pii a, Pii b) -> bool {return a.first > b.first;});cur = cover.begin();uf.Init();ucnt = 0; for (auto q : qv) {int p = q.p, t = q.t, id = q.id;while (cur != cover.end() && cur->first > p) {ucnt += uf.Try_to_unite(cur->first, cur->second);++cur;}int timel = uf.Get_time(), tmpcnt = 0;for (auto e : vec) {if (e.l <= t && e.r >= t && e.x > p) {tmpcnt += uf.Try_to_unite(e.x, e.y);}}ans[q.id] += (n - p) - ucnt - tmpcnt;uf.Roll_back(timel);}}return ans;
}// void Test () {
// int N, C, Q;
// cin >> N >> C >> Q;
// vector<int> T, X, Y;
// for (int i = 0, t, x, y; i < C; ++i) {
// cin >> t >> x >> y;
// T.push_back(t), X.push_back(x), Y.push_back(y);
// }
// vector<int> W, P;
// for (int i = 0, w, p; i < Q; ++i) {
// cin >> w >> p;
// W.push_back(w), P.push_back(p);
// }
// vector<int> ans = simulateCollapse(N, T, X, Y, W, P);
// for (auto i : ans) {
// cout << i << '\n';
// }
// }// int main () { Test(); }
T4 Xylophone
题意：你要猜一个隐藏的 \(1 \sim n\) 的排列 \(p\)，保证 \(p\) 的最小值出现在最大值左边。
你可以向交互库提出若干次询问，每次询问你可以给出一个区间 \([l, r]\)，交互库会返回 \(p_l, p_{l + 1}, \ldots, p_r\) 中最大数和最小数之差。
你需要通过不超过 \(10^4\) 询问得到排列 \(p\)。
\(n \le 5 \times 10^3\)。
考虑先对于每个 \(i \in [2, n]\)，询问 \((i, i - 1)\)，令 \(b_i = p_i - p_{i - 1}\)，此时我们就得到了 \(|b_2|, |b_3|, \ldots, |b_n|\)。
假设我们通过某种方式得到了 \(b_2, b_3, \ldots, b_n\)，那么这道题就做完了。考虑随便钦定一个 \(p_1\)，我们就可以得到 \(p_1, p_2, \ldots, p_n\) 的相对关系，那么 \(p\) 构成一个 \(x + 1, x + 2, \ldots, x + n\) 的排列，将整个排列偏移 \(x\) 即可还原 \(p\)。
考虑如何还原出 \(p\)。我们进一步 \(\forall i \in [3, n]\)，询问 \((i - 2, i)\)，那么我们就得到了 \(c_i = \max(|b_i|, |b_{i - 1}|, |b_{i - 1} + b_i|)\)，因为 \(b_i > 0\)，所以 \(b_{i - 1}\) 和 \(b_i\) 同号当且仅当 \(c_i = |b_i| + |b_{i - 1}|\)。此时我们还原出了 \(i \in [3, n]\) 时 \(b_{i - 1}\) 和 \(b_i\) 符号的相对关系。
此时我们只需枚举 \(b_2 = -1/1\) 即可得到 \(b_3, b_4, \ldots, b_n\)。此时我们还原可以得到两个 \(a\)，此时满足最小值出现在最大值左侧的就是真正的 \(a\)。
为什么恰有一个合法？考虑对于两个 \(a\)，将所有点 \((i, a_i)\) 画在二维平面上，那么每次 \(i\) 向 \(i + 1\) 移动的过程，两个序高度的变化量是相反的，所以我们最终会得到两条形态对偶的折线。那么它们满足一条折线的峰值恰是另一条折线的谷值，所以一定是恰好一个满足条件。
时间复杂度 \(O(n)\)。询问次数 \(2n - 3\)。
Code
#include "xylophone.h"
#include <iostream>
#include <algorithm>using namespace std;void solve (int N);
int query (int s, int t);
void answer (int i, int a);const int kN = 5e3 + 5; int a[kN], b[kN], sgn[kN], c[kN], e[kN];void solve (int N) {for (int i = 2; i <= N; ++i) {b[i] = query(i - 1, i);}for (int i = 3; i <= N; ++i) {c[i] = query(i - 2, i);}for (int i = 3; i <= N; ++i) {sgn[i] = (c[i] == b[i] + b[i - 1] ? 1 : -1);}for (int o = 0; o < 2; ++o) {e[2] = (!o ? -1 : 1); for (int i = 3; i <= N; ++i) {e[i] = e[i - 1] * sgn[i];}for (int i = 2; i <= N; ++i) {e[i] *= b[i];}a[1] = 0; for (int i = 2; i <= N; ++i) { a[i] = a[i - 1] + e[i];}int del = -*min_element(a + 1, a + N + 1) + 1;for (int i = 1; i <= N; ++i) {a[i] += del;}int mi = min_element(a + 1, a + N + 1) - a, mx = max_element(a + 1, a + N + 1) - a; if (mi < mx) {for (int i = 1; i <= N; ++i) {answer(i, a[i]);}return; }}
}
