#include <bits/stdc++.h>
#include "meetings.h"
using namespace std;
mt19937 Rand(time(0));
inline void answer(int x, int y) {
if (x > y) swap(x, y);
Bridge(x, y);
}
void dfs(vector<int> a, int x, int y) {
if (a.empty()) return answer(x, y);
if (a.size() == 1) return answer(x, a[0]), answer(a[0], y);
int mid = a[Rand() % a.size()];
vector<int> al, ar;
for (int i : a) if (i != mid) {
if (Query(x, mid, i) == i) al.emplace_back(i);
else ar.emplace_back(i);
}
dfs(al, x, mid); dfs(ar, mid, y);
}
void solve(vector<int> a) {
if (a.size() <= 1) return;
int n = a.size(), x = a[Rand() % n], y = a[Rand() % n];
while (x == y) y = a[Rand() % n];
map<int, vector<int>> mp;
mp[x].emplace_back(x); mp[y].emplace_back(y);
for (int i : a) if (i != x && i != y) mp[Query(x, y, i)].emplace_back(i);
vector<int> chain;
for (auto [p, q] : mp) if (p != x && p != y) chain.emplace_back(p);
dfs(chain, x, y);
for (auto [p, q] : mp) solve(q);
}
void Solve(int n) {
vector<int> a(n);
for (int i = 0; i < n; ++i) a[i] = i;
solve(a);
}
C. 馕
Portal.
一个长度为 L 的激光剑被分为 L 段，每段一个单位长度，第 i 段为第 j 种口味。
构造一个顺序，给每个人划分一段激光剑，每个人获得一定的长度。
构造一种方案，每个人分泌的多巴胺大于自己吃掉整个激光剑的多巴胺的 $\frac 1 n$，或者报告无解。
$n,L\le 2000$。
---
比较显然的是，考虑让每个人恰好吃他总收益的 $\frac 1 n$。考虑每个人的 $n$ 等分点，贪心取所有人中 $n$ 等分点最短的一段，然后直接划给这个人，因为他消耗的最少，这样一定是不劣的。
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long i64;
typedef __int128 lll;
int n, L, c[2005];
i64 v[2005][2005];
struct Frac {
i64 x, y;
Frac(i64 x = 1, i64 y = 0) : x(x), y(y) {}
bool operator< (const Frac &a) const { return (lll)x * a.y < (lll)a.x * y; }
bool operator>= (const Frac &a) const { return (lll)x * a.y >= (lll)a.x * y; }
} a[2005][2005]; // 第 i 个人的第 j 等分段在哪里结束
int main(void) {
ios::sync_with_stdio(0);
cin >> n >> L;
for (int i = 1; i <= n; ++i) for (int j = 1; j <= L; ++j) cin >> v[i][j];
for (int id = 1; id <= n; ++id) {
i64 s = 0, cur = 0;
for (int i = 1; i <= L; ++i) s += v[id][i];
int j = 1;
for (int i = 1; i <= L; ++i) {
while (j <= n && Frac(cur + v[id][i], 1) >= Frac(s * j, n))
a[id][j] = Frac(s * j - cur * n + n * v[id][i] * (i - 1), n * v[id][i]),
++j;
if (j > n) break;
cur += v[id][i];
}
}
static bool vis[2005]; memset(vis, 0, sizeof vis);
for (int i = 1; i <= n; ++i) {
Frac res; int t = 0;
for (int j = 1; j <= n; ++j) if (!vis[j] && a[j][i] < res)
res = a[j][i], t = j;
vis[t] = 1; c[i] = t;
if (i != n) cout << res.x << " " << res.y << "\n";
}
for (int i = 1; i <= n; ++i) cout << c[i] << " \n"[i == n];
return 0;
}
```
### Day2
[A](https://qoj.ac/problem/65)，[B](https://qoj.ac/problem/66)，[C](https://qoj.ac/problem/67)。
#### A. * 两个天线
[Portal](https://loj.ac/p/3033).
$n$ 个天线，相邻距离为 $1$，高度为 $H_i$。天线 $i$ 向天线 $j$ 可以发消息，通信成本为 $|H_i-H_j|$，当且仅当它们之间的距离 $D_{i,j}\in [A_i,B_i]$。
多次询问区间中可以**相互**发送信息的天线的最大值。
$n\le 2\times 10^5$。
---
考虑离线，所有询问按 $R$ 排序。绝对值不好处理，拆了正反各做一遍。
每次新增一个可行的 $j$，将可行的 $i$ 加入答案集合。对 $y$ 来说合法的 $x$ 区间是 $[y-B_y,y-A_y]$，$x$ 需要满足 $y\in [x+A_x,x+B_x]$，典型的扫描线。
```cpp
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
const int N = 800000;
int mxA[800005], mxB[800005], tag[800005];
void clear(void) {
fill(mxA + 1, mxA + N + 1, -INF);
fill(mxB + 1, mxB + N + 1, -INF);
fill(tag + 1, tag + N + 1, -INF);
}
inline void pushup(int o) {
mxA[o] = max(mxA[o << 1], mxA[o << 1 | 1]);
mxB[o] = max(mxB[o << 1], mxB[o << 1 | 1]);
}
inline void maketag(int o, int k) {
tag[o] = max(tag[o], k);
mxB[o] = max(mxB[o], mxA[o] + k);
}
inline void pushdown(int o) {
maketag(o << 1, tag[o]); maketag(o << 1 | 1, tag[o]);
tag[o] = -INF;
}
void updateA(int o, int l, int r, int x, int k) {
if (l == r) return mxA[o] = k, void();
pushdown(o); int mid = l + r >> 1;
if (x <= mid) updateA(o << 1, l, mid, x, k);
else updateA(o << 1 | 1, mid + 1, r, x, k);
pushup(o);
}
void updateB(int o, int l, int r, int x, int y, int v) {
if (x <= l && r <= y) return maketag(o, v), void();
pushdown(o); int mid = l + r >> 1;
if (x <= mid) updateB(o << 1, l, mid, x, y, v);
if (mid < y) updateB(o << 1 | 1, mid + 1, r, x, y, v);
pushup(o);
}
int query(int o, int l, int r, int x, int y) {
if (x <= l && r <= y) return mxB[o];
pushdown(o); int mid = l + r >> 1, res = -INF;
if (x <= mid) res = max(res, query(o << 1, l, mid, x, y));
if (mid < y) res = max(res, query(o << 1 | 1, mid + 1, r, x, y));
return res;
}
int n, q;
int h[200005], a[200005], b[200005];
int l[200005], r[200005], ans[200005];
vector<pair<int, int> > Q[200005], A[200005];
void solve(void) {
for (int i = 1; i <= n; ++i) Q[i].clear(), A[i].clear();
for (int i = 1; i <= q; ++i) Q[r[i]].emplace_back(l[i], i);
for (int i = 1; i <= n; ++i) {
if (i + a[i] <= n) A[i + a[i]].emplace_back(i, h[i]);
if (i + b[i] + 1 <= n) A[i + b[i] + 1].emplace_back(i, -INF);
}
for (int i = 1; i <= n; ++i) {
for (auto [p, v] : A[i]) updateA(1, 1, n, p, v);
if (i - a[i] >= 1) updateB(1, 1, n, max(1, i - b[i]), i - a[i], -h[i]);
for (auto [l, id] : Q[i]) ans[id] = max(ans[id], query(1, 1, n, l, i));
}
}
int main(void) {
ios::sync_with_stdio(0);
cin >> n;
for (int i = 1; i <= n; ++i) cin >> h[i] >> a[i] >> b[i];
cin >> q; memset(ans, -1, sizeof ans);
for (int i = 1; i <= q; ++i) cin >> l[i] >> r[i];
clear(); solve();
reverse(h + 1, h + n + 1); reverse(a + 1, a + n + 1); reverse(b + 1, b + n + 1);
for (int i = 1; i <= q; ++i) l[i] = n - l[i] + 1, r[i] = n - r[i] + 1, swap(l[i], r[i]);
clear(); solve();
for (int i = 1; i <= q; ++i) cout << ans[i] << "\n";
return 0;
}
```
#### B. ** 两种料理
[Portal](https://loj.ac/p/3034).
你要烹饪两道料理：**闪耀的芝士蛋挞** 和 **深潜的极寒冰沙**，分别有 $n,m$ 到工序，需要的时间是 $a_1,\cdots,a_n$ 和 $b_1,\cdots,b_m$ 分钟。
制作这两道料理都非常困难：一个步骤开始之后不能中断。到最后，你必须做完这两道料理。
如果你在比赛的前 $s_i$ 分钟完成了 闪耀的芝士蛋挞 的第 $i$ 个制作步骤，那么你可以获得 $p_i$ 的分数。
同理，在 $t_j$ 分钟前完成 深潜的极寒冰沙 的第 $j$ 个制作步骤可获得 $q_j$ 的分数。
问最大得分。$n,m\le 10^6$，分数可能是负的。
---
太精彩啦！巨大的 $n,m$ 让人想只对闪耀的芝士蛋挞（以下称为 A 料理）DP，直接计算深潜的极寒冰沙（以下称为 B 料理）的贡献。但是做不了。
设 $f_{i,j}$ 代表完成 A 料理 的前 $i$ 步，B 料理的前 $j$ 步的最大得分。看上去它的尽头就是 $O(nm)$，实则不然！
可以看作网格图上从 $(0,0)$ 走到 $(n,m)$，向右走代表完成 A 料理的一个步骤，向下走代表完成 B 料理的一个步骤。求出 $a,b$ 的前缀和 $sa,sb$。现在将贡献映射到点上，对于每个 $s_i$，找到最大的 $sb_j\le s_i-sa_i$ 的格点 $(i,j)$，它在路径的左上方（或路径上）便有贡献。同理对 $t_j$ 找到最大的 $sa_i\le t_j-sb_j$，那么它在路径的右下放就有贡献。
想办法将两种贡献点改成一样的。容斥！我们将 $p$ 先全部加上，然后减去严格在下面的。也就是说，将 $(i-1,j+1)$ 的贡献标记为 $-p_i$。也就是说，现在只需要最大化右下（包括路径上）的权值和。
每次考虑对前一列进行计算（先将 $y=0$ 和 $x=n$ 判掉）：
$$
f(x,y)=\max\{f(x,y-1),f(x-1,y)+\sum_{i=1}^y v(x-1,i)\}
$$
后缀加，前缀取 $\max$，维护差分数组，同 $x$ 的点按照 $y$ 从大到小加入，正数直接加入差分数组，负数的要找到这个 $y$ 让后往上跑直到这个负的贡献没掉。
使用 `map` 维护，时间复杂度 $O((n+m)\log (n+m))$。
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long i64;
const int N = 1000005;
int n, m;
i64 a[N], s[N], p[N], b[N], t[N], q[N], ans;
vector<pair<int, i64>> node[N];
void tag(int x, int y, i64 v) {
if (x < 0 | y > m) return;
if (x == n || y == 0) return ans += v, void();
node[x].emplace_back(y, v);
}
int main(void) {
ios::sync_with_stdio(0);
cin >> n >> m;
for (int i = 1; i <= n; ++i) cin >> a[i] >> s[i] >> p[i], a[i] += a[i - 1];
for (int i = 1; i <= m; ++i) cin >> b[i] >> t[i] >> q[i], b[i] += b[i - 1];
for (int i = 1; i <= n; ++i) {
int j = upper_bound(b, b + m + 1, s[i] - a[i]) - b - 1;
ans += p[i];
tag(i - 1, j + 1, -p[i]);
}
for (int j = 1; j <= m; ++j) {
int i = upper_bound(a, a + n + 1, t[j] - b[j]) - a - 1;
tag(i, j, q[j]);
}
map<int, i64> c;
for (int x = 0; x < n; ++x) {
sort(node[x].begin(), node[x].end(), greater<pair<int, i64>>());
for (auto [y, v] : node[x]) {
if (v > 0) c[y] += v;
else {
v = -v;
auto it = c.lower_bound(y);
while (v > 0 && it != c.end()) {
if (v >= it->second) v -= it->second, it = c.erase(it);
else { it->second -= v; break; }
}
}
}
}
for (auto [y, v] : c) ans += v;
cout << ans << "\n";
return 0;
}
```
#### C. 两种交通工具
通信题。
猜猜我是否还能回来做！对不起了！
### Day3
[A](https://qoj.ac/problem/68)，[B](https://qoj.ac/problem/69)，[C](https://qoj.ac/problem/70)。
#### A. * 指定城市
[Portal](https://loj.ac/p/3036).
给定一棵树，双向边，每条边两个方向的权值不同。多次询问 $k$，表示选出 $k$ 个点，依次将以每个点为根的内向树边权赋值为 $0$，需要求出最后树的边权之和的最小值。要求 $O(n)$。
---
$w_x$ 代表以 $x$ 为根的内向树边权和，换根 DP 求出，$k=1$ 被解决。
贪心地想，$k>1$ 一定是再选一条链，长剖贪心即可。
但是 $k=2$ 时这一点不成立，需要使用换根 DP 解决。换完根之后将直径缩点，然后长剖贪心。
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long i64;
int n, m; i64 sum, ans[200005];
struct edge {
int v, c, d;
edge(int v = 0, int c = 0, int d = 0) : v(v), c(c), d(d) {}
};
vector<edge> G[200005];
i64 w[200005];
void dfs1(int x, int fa) { for (auto [y, c, d] : G[x]) if (y != fa) dfs1(y, x), w[x] += w[y] + d; }
void dfs2(int x, int fa) { for (auto [y, c, d] : G[x]) if (y != fa) w[y] = w[x] - d + c, dfs2(y, x); }
int f[200005]; i64 dis[200005];
void DFS(int x, int fa) {
f[x] = fa;
for (auto [y, c, d] : G[x]) if (y != fa) dis[y] = dis[x] + c + d, DFS(y, x);
}
bool vis[200005];
vector<i64> c;
i64 solve(int x, int fa) {
i64 res = 0;
for (auto [y, c, d] : G[x]) if (y != fa) {
i64 w = solve(y, x) + c;
if (!res) res = w;
else ::c.emplace_back(min(res, w)), res = max(res, w);
}
return res;
}
int main(void) {
ios::sync_with_stdio(0);
cin >> n;
for (int i = 1; i < n; ++i) {
int u, v, c, d; cin >> u >> v >> c >> d; sum += c + d;
G[u].emplace_back(v, c, d); G[v].emplace_back(u, d, c);
} dfs1(1, 0); dfs2(1, 0);
for (int i = 1; i <= n; ++i) ans[1] = max(ans[1], w[i]);
DFS(1, 0); int A = 1;
for (int i = 1; i <= n; ++i) if (dis[i] + w[i] > dis[A] + w[A]) A = i;
dis[A] = 0; DFS(A, 0); int B = 1;
for (int i = 1; i <= n; ++i) if (dis[i] + w[i] > dis[B] + w[B]) B = i;
ans[2] = (w[A] + w[B] + dis[B]) / 2; // +1
int x = B; while (x) vis[x] = 1, x = f[x]; x = B;
while (x) {
for (auto [y, _c, _d] : G[x]) if (!vis[y])
c.emplace_back(solve(y, x) + _c);
x = f[x];
}
sort(c.begin(), c.end(), greater<i64>());
int t = 2;
for (i64 x : c) ans[t + 1] = ans[t] + x, ++t;
while (t < n) ans[t + 1] = ans[t], ++t;
for (cin >> m; m--; ) { int x; cin >> x; cout << sum - ans[x] << "\n"; }
return 0;
}
```
#### B. 灯光表演
[Portal](https://loj.ac/p/3037).
$n$ 个灯有初始状态，一次操作可以区间打开/关闭/翻转，问变成目标状态的最小操作次数。$n\le 10^6$。
---
手玩得到基础结论：
- 区间异或操作可以放到所有赋值操作之后；
- 区间赋值操作互不相交。
得到最后形态之后，区间异或操作次数为 $s'\operatorname{xor} t$ 的极长 $1$ 段数。
$f_{i,0/1/2}$ 代表以 $i$ 结尾，第 $i$ 位用 $0$、$1$、保持原样 来覆盖的最小代价。枚举上一位情况即可实现 $O(n)$ 转移。
```cpp
#include <bits/stdc++.h>
using namespace std;
int n;
char s[1000005], t[1000005];
int f[1000005][3];
int main(void) {
scanf("%d%s%s", &n, s + 1, t + 1);
memset(f, 0x3f, sizeof f);
f[1][0] = 1 + (t[1] == '1');
f[1][1] = 1 + (t[1] == '0');
f[1][2] = (s[1] != t[1]);
for (int i = 2; i <= n; ++i) {
if (t[i] == '0') f[i][0] = min({f[i - 1][0], f[i - 1][1] + 1, f[i - 1][2] + 1});
else f[i][0] = min({f[i - 1][0] + (t[i - 1] == '0'), f[i - 1][1] + (t[i - 1] == '1') + 1, f[i - 1][2] + (s[i - 1] == t[i - 1]) + 1});
if (t[i] == '1') f[i][1] = min({f[i - 1][0] + 1, f[i - 1][1], f[i - 1][2] + 1});
else f[i][1] = min({f[i - 1][0] + (t[i - 1] == '0') + 1, f[i - 1][1] + (t[i - 1] == '1'), f[i - 1][2] + (s[i - 1] == t[i - 1]) + 1});
if (s[i] == t[i]) f[i][2] = min({f[i - 1][0], f[i - 1][1], f[i - 1][2]});
else f[i][2] = min({f[i - 1][0] + (t[i - 1] == '0'), f[i - 1][1] + (t[i - 1] == '1'), f[i - 1][2] + (s[i - 1] == t[i - 1])});
}
printf("%d\n", min({f[n][0], f[n][1], f[n][2]}));
return 0;
}
```
#### * C. 时间旅人
[Portal](https://loj.ac/p/3038).
$n$ 个点，第 $i$ 条路连接第 $i$ 和 $i+1$ 个点。第 $i$ 条路在 $[l_i,r_i]$ 时开放，通过一条路需要 $1$ 的时间，行动需要保证在穿梭的过程中道路一直是开放的。
Bitaro 是能穿梭时间的河狸，它在城市可以穿梭回一秒前。给定 $Q$ 次询问：
- 改变 $i$ 道路的开放时间。
- 假设 $B$ 时刻它在 $A$ 城，问最少需要进行多少次时间旅行才能在 $D$ 时刻前到达 $C$ 城。
$n,Q\le 3\times 10^5$，时间在 $10^9$ 级别。
---
显然走的方式很呆板：能走就走，不能走就时间旅行。现在假设 $A<C$。
设 $y$ 时刻的 $x$ 城市代表 $(x,y)$，套路地，为了避免行走时时间流逝的自然影响，将其改成 $(x,y-x)$。
用 $(a,b,c)$ 表示行动，$a$ 为开始时刻，$b$ 为结束时刻，$c$ 为时间倒流次数。$(L,R)$ 代表这条道路只能在 $[L,R]$ 时通过。现在考虑如何合并：
- 两个二元：如果有交集则取交集，否则可以转化为三元组。
- 一二一三：观察二元组和 $a$ 的关系即可算出。
- 两个三元：计算中间时间穿越的次数即可。
最终答案用起终点的两个三元组加上中间路径的三元组即可得到。具有结合律，可以使用线段树维护。$A>C$ 的情况是对称的。时间复杂度 $O((n+q)\log n)$。
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long i64;
const int INF = 1e9;
int n, q;
int l[300005], r[300005];
struct Node {
int l, r; i64 val;
Node(int l = -INF, int r = INF, i64 val = -1) : l(l), r(r), val(val) {}
friend Node operator+ (const Node &a, const Node &b) {
if (a.val == -1 && b.val == -1) {
if (a.l > b.r) return Node(a.l, b.r, a.l - b.r);
if (a.r < b.l) return Node(a.r, b.l, 0);
return Node(max(a.l, b.l), min(a.r, b.r));
}
if (a.val == -1) {
if (b.l < a.l) return Node(a.l, b.r, b.val + a.l - b.l);
if (b.l > a.r) return Node(a.r, b.r, b.val);
return b;
}
if (b.val == -1) {
if (a.r < b.l) return Node(a.l, b.l, a.val);
if (a.r > b.r) return Node(a.l, b.r, a.val + a.r - b.r);
return a;
}
return Node(a.l, b.r, a.val + b.val + max(0, a.r - b.l));
}
};
struct Segment_Tree {
Node T[1200005];
void update(int o, int l, int r, int p, int x, int y) {
if (l == r) return T[o] = Node(x, y, -1), void();
int mid = l + r >> 1;
if (p <= mid) update(o << 1, l, mid, p, x, y);
else update(o << 1 | 1, mid + 1, r, p, x, y);
T[o] = T[o << 1] + T[o << 1 | 1];
}
void update(int p, int x, int y) { update(1, 1, n - 1, p, x, y); }
Node query(int o, int l, int r, int x, int y) {
if (x <= l && r <= y) return T[o];
int mid = l + r >> 1;
if (y <= mid) return query(o << 1, l, mid, x, y);
if (mid < x) return query(o << 1 | 1, mid + 1, r, x, y);
return query(o << 1, l, mid, x, y) + query(o << 1 | 1, mid + 1, r, x, y);
}
Node query(int x, int y) { return query(1, 1, n - 1, x, y); }
} tL, tR;
int main(void) {
ios::sync_with_stdio(0);
cin >> n >> q;
for (int i = 1; i < n; ++i) {
cin >> l[i] >> r[i];
tL.update(i, l[i] - i, r[i] - 1 - i);
}
reverse(l + 1, l + n); reverse(r + 1, r + n);
for (int i = 1; i < n; ++i) tR.update(i, l[i] - i, r[i] - 1 - i);
while (q--) {
int op; cin >> op;
if (op == 1) {
int p, l, r; cin >> p >> l >> r;
tL.update(p, l - p, r - 1 - p);
p = n - p; tR.update(p, l - p, r - 1 - p);
} else {
int a, b, c, d; cin >> a >> b >> c >> d;
if (a < c) cout << max(0ll, (Node(b - a, b - a) + tL.query(a, c - 1) + Node(d - c, d - c)).val) << "\n";
else if (a == c) cout << max(0, b - d) << "\n";
else {
a = n - a + 1; c = n - c + 1;
cout << max(0ll, (Node(b - a, b - a) + tR.query(a, c - 1) + Node(d - c, d - c)).val) << "\n";
}
}
}
return 0;
}
```
### Day4
[A](https://qoj.ac/problem/71)，[B](https://qoj.ac/problem/72)，[C](https://qoj.ac/problem/73)。
#### A. * 蛋糕拼接 3
[Portal](https://loj.ac/p/3039).
$n(n\le 2\times 10^5)$ 块蛋糕有自己的价值 $V_i$ 和颜色 $C_i$，需要选择 $M$ 块互不相同的蛋糕拼成一个环，蛋糕的美味程度为：
$$
\sum_{j=1}^M V_{k_j}-\sum_{j=1}|C_{k_j}-C_{k_j \bmod M+1}|
$$
给定 $M$，求出一个 $k$，问最大的美味程度。
---
如果选定了 $k$，那么按照 $C$ 排序算出贡献。
打表发现具有决策单调性，分治计算即可。
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long i64;
const int N = 200005;
int n, m, nn;
struct Cake {
int v, c;
bool operator< (const Cake &a) const { return c < a.c; }
} a[N];
int b[N];
struct Node {
int ls, rs;
int siz; i64 sum;
} T[N * 40];
int rt[N], tot;
int update(int pre, int l, int r, int x, int v) {
int o = ++tot; T[o] = T[pre]; ++T[o].siz; T[o].sum += v;
if (l == r) return o;
int mid = l + r >> 1;
if (x <= mid) T[o].ls = update(T[pre].ls, l, mid, x, v);
else T[o].rs = update(T[pre].rs, mid + 1, r, x, v);
return o;
}
i64 query(int p, int q, int l, int r, int k) { // 值域在 [l, r] 中的 V 最大 k 个的答案
if (l == r) return 1ll * k * b[l];
int mid = l + r >> 1, res = T[T[q].rs].siz - T[T[p].rs].siz;
if (res >= k) return query(T[p].rs, T[q].rs, mid + 1, r, k);
return query(T[p].ls, T[q].ls, l, mid, k - res) + T[T[q].rs].sum - T[T[p].rs].sum;
}
i64 ans = -1e18;
inline i64 calc(int l, int r) { return query(rt[l - 1], rt[r], 1, nn, m) - 2 * (a[r].c - a[l].c); }
void solve(int l, int r, int L, int R) { // 决策区间 [L, R]
if (l > r) return;
int mid = l + r >> 1, p = 0, RR = min(R, mid - m + 1);
i64 mx = -1e18;
for (int i = L; i <= RR; ++i) {
i64 w = calc(i, mid);
if (w > mx) mx = w, p = i;
} ans = max(ans, mx);
solve(l, mid - 1, L, p); solve(mid + 1, r, p, R);
}
int main(void) {
ios::sync_with_stdio(0);
cin >> n >> m;
for (int i = 1; i <= n; ++i) cin >> a[i].v >> a[i].c, b[i] = a[i].v;
sort(b + 1, b + n + 1); sort(a + 1, a + n + 1);
nn = unique(b + 1, b + n + 1) - (b + 1);
for (int i = 1; i <= n; ++i) rt[i] = update(rt[i - 1], 1, nn, lower_bound(b + 1, b + nn + 1, a[i].v) - b, a[i].v);
solve(m, n, 1, n);
cout << ans << "\n";
return 0;
}
```
#### B. 合并
[Portal](https://loj.ac/p/3040).
$n(n\le 2\times 10^5)$ 个点的树，每个点有颜色，一次操作可以将两种操作并为一种颜色。
一棵树是不合法的，当且仅当存在一条边，没有任何一种颜色存在于两边。问使得树合法的最小操作数。
---
合并所有的两个相同颜色构成的链上的边，最后合并所有度数为 $1$ 的点，答案是 $\left\lceil \frac c 2 \right\rceil$。时间复杂度为 $O(n\log n)$（并查集只路径压缩）。
```cpp
#include <bits/stdc++.h>
using namespace std;
int n, k, a[500005];
vector<int> G[500005];
int f[500005], dep[500005];
int bin[500005];
int find(int x) { return bin[x] == x ? x : bin[x] = find(bin[x]); }
void dfs(int x, int fa) {
dep[x] = dep[f[x] = fa] + 1; bin[x] = x;
for (int y : G[x]) if (y != fa) dfs(y, x);
}
int lst[500005];
void calc(int x, int y) {
x = find(x); y = find(y);
while (x != y) {
if (dep[x] < dep[y]) swap(x, y);
bin[x] = find(bin[f[x]]);
x = find(x);
}
}
int main(void) {
ios::sync_with_stdio(0);
cin >> n >> k;
for (int i = 1; i < n; ++i) {
int u, v; cin >> u >> v;
G[u].emplace_back(v); G[v].emplace_back(u);
} dfs(1, 0);
for (int i = 1; i <= n; ++i) {
cin >> a[i];
if (lst[a[i]]) calc(lst[a[i]], i);
lst[a[i]] = i;
}
static int deg[500005]; memset(deg, 0, sizeof deg);
for (int i = 2; i <= n; ++i) {
int x = find(f[i]), y = find(i);
if (x != y) ++deg[x], ++deg[y];
}
int cnt = 0;
for (int i = 1; i <= n; ++i) cnt += (deg[i] == 1);
cout << (cnt == 1 ? 0 : (cnt + 1) / 2) << "\n";
return 0;
}
```
#### * C. 矿物
[Portal](https://loj.ac/p/3041).
$2n(n\le 4.3\times 10^4)$ 个球，$n$ 种颜色每种恰好出现两次，需要将球配对。可以询问 $10^6$ 次：
- 插入/删除一个球，得到颜色种类数。
---
看到这个数据范围考虑分治。`solve(A, B)` 表示所有相同颜色的球一个在 $A$，另一个在 $B$。只需要对 $A$ 的前一半问一次，然后对 $B$ 全部问一次，就可以得到 $B$ 中的是否归 $A$ 的前一半的。
卡常卡到丧心病狂，中点分治不一定是最优，发现稍微小一点表现更好，随机偏移一下。同时，注意不要浪费非必要的询问。
```cpp
#include <bits/stdc++.h>
#include "minerals.h"
using namespace std;
mt19937 Rand(time(0));
double rnd(double l, double r) {
return uniform_real_distribution<double>(l, r)(Rand);
}
bool query(int x) {
static int last = 0;
int v = Query(x);
if (v == last) return 0;
return last = v, 1;
}
void solve(vector<int> a, vector<int> b, bool in) {
if (a.size() == 1) return Answer(a[0], b[0]);
vector<int> bl, br;
int m = max(1, int(a.size() * rnd(0.3, 0.5)));
for (int i = 0; i < m; ++i) query(a[i]);
for (int i : b)
if (bl.size() == m) br.emplace_back(i);
else if (br.size() == a.size() - m) bl.emplace_back(i);
else if (query(i) == in) bl.emplace_back(i);
else br.emplace_back(i);
solve(vector<int>(a.begin(), a.begin() + m), bl, !in);
solve(vector<int>(a.begin() + m, a.end()), br, in);
}
void Solve(int n) {
n <<= 1; vector<int> a, b;
static int id[200005];
for (int i = 1; i <= n; ++i) id[i] = i;
shuffle(id + 1, id + n + 1, Rand);
for (int i = 1; i <= n; ++i)
if (query(id[i])) a.emplace_back(id[i]);
else b.emplace_back(id[i]);
solve(a, b, 1);
}
```
### 总结
10/8 机房集体 CF 被所有人干烂了……
大家都好强……