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\)。所以答案显然为
\[\max\limits_{i = 1}^n \bigg{(}\sum\limits_{j = 1}^{i- 1} [a_j > a_i] \bigg{)} \]对于这个直接树套树维护动态二维偏序，时间复杂度 \(O(n \log^2 n)\)。无法通过。
考虑对于一个 \(i\)，若存在 \(k > i\) 使得 \(a_k < a_i\)，那么 \(k\) 相对于 \(i\) 不劣，此时我们可以不计算 \(i\) 的贡献。也就是说，计算答案时只需考虑所有后缀最小值。
那么我们考虑对限制放缩，对于一个数 \(i\)，我们直接钦定 \(i\) 后面的数全部大于 \(i\)，此时对于后缀 \(\min\) 的位置答案不变，对于非后缀 \(\min\) 的位置答案变小了，所以这样做是对的、那么我们要计算的就是：
\[\max\limits_{i = 1}^n \bigg{(}\sum\limits_{j = 1}^{n} [a_j > a_i] \bigg{)} - (n - i) \]这个东西考虑用权值线段树维护，一个数修改时的影响就是一段前缀加或减，这个都好维护。
时间复杂度 \(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\) 的转移方程
\[ f_{u, 0} = \min(f_{v, 0}, f_{v, 1} + 1) + g_{u, 0} + [a_u = 1]\infty \\ f_{u ,1} = \min(f_{v, 1}, f_{v, 0} + 1) + g_{u, 1} + [a_u = 2]\infty \]其中 \(a_u = 1\) 表示 \(u\) 结点处为猫，\(a_u = 2\) 表示 \(u\) 结点处为狗。我们将转移写成 \((\min, +)\) 矩阵乘法的形式：
\[ \begin{bmatrix} g_{u, 0} + [a_u = 1]\infty & g_{u, 0} + 1 + [a_u = 1]\infty \\ g_{u, 1} + 1 + [a_u = 2]\infty & g_{u, 1} + [a_u = 2]\infty \end{bmatrix} \ast \begin{bmatrix} f_{v, 0} \\ f_{v, 1} \end{bmatrix} = \begin{bmatrix} f_{u, 0} \\ f_{u, 1} \end{bmatrix} \]剩下的就是动态树分治板子了，对于重链线段树维护转移矩阵，对于轻边暴力跳即可。
时间复杂度 \(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 {
// Remake
n = 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 merge
for (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;
}
}
}