Codeforces Round 932 (Div. 2)
| ID | Difficulty (0-5) | Topic | Status | Code |
|---|---|---|---|---|
| A | 0 | Greedy | Solved | A.cpp |
| B | 0 | MEX | Solved | B.cpp |
| C | 2 | Greedy | Solved | C.cpp |
| D | 1 | Counting | Solved | D.cpp |
| E | 3 | Segment Tree, Greedy | Upsolved | E.cpp |
| F | 3 | Kruskal, DFS order | Solved | F.cpp |
B. Informatics in MAC
两个 MEX 相同的集合合并之后 MEX 不变。所以有解一定可以划分成两个集合。
C. Messenger in MAC
按 B 升序排序后，枚举选中区间，则至少有 $b_r-b_l$ 的代价。
然后对区间内的 $a$ 排序做贪心即可，复杂度 $O(n^3\log n)$ 。
注意到随着右端点的增加留给 $a$ 的空间会变少，因此可以用堆维护贪心的过程，随着右端点变大，之前删除的数不可能放回来。这样固定 $l$ 每个数只会插入删除各一次，复杂度就降低到了 $O(n^2\log n)$ 。
注意考虑代价的时候不能带上 $a_l+a_r$ ，有可能某个 $a_r$ 很大导致误删了前面的 $a$ 。
D. Exam in MAC
计数不合法。注意到数重的两个 $s_i$ 奇偶性一定相同即可。
E. Distance Learning Courses in MAC
给定 $n$ 个区间 $[l_i,r_i]$ ，每个区间内选一个点 $x_i\in [l_i,r_i]$ ，使得所有 $x_i$ 的按位或最大。
考虑没有左端点的约束，有一个贪心过程：
- 令 $cnt[x]$ 表示所有的 $r_i$ 中有多少个第 $x$ 位是 $1$ ，然后从高往低贪心，如果 $cnt[x]=1$ 则这一位是 $1$ ，$cnt[x]=0$ 则这一位是 $0$ ，直到遇到 $cnt[x]>1$ ，则从第 $x$ 位往下都可以变成 $1$ （退位一个 $2^x$）。
加上左端点约束时，考虑 $l_i,r_i$ 的二进制表达lcp，这部分是不能改变的。对于剩下的部分，注意到对齐后一定是 $r_i$ 以 $1$ 开头而 $l_i$ 以 $0$ 开头，这相当于允许 $r_i$ 的高位退位，$l_i$ 的约束相当于不存在了。
因此线段树维护区间 lcp 的或，以及剩余的 $r_i$ 各位的 $cnt$ ，查询出区间信息后跑一遍上面的贪心即可。
总复杂度 $O(n\log n)$ 。
F. Andrey’s Tree
给一棵树，对每个结点 $v$ 考虑：
删除节点 $v$ ，然后把形成的若干连通块重新连成一棵树的最小代价。
增加一条连接 $(a,b)$ 的边的代价是 $|a-b|$ 。
考虑 Kruskal 的过程，我们先考虑所有边权为 $1$ 的边，一定可以把 $[1,v-1]$ 和 $[v+1,n]$ 分别连通。
如果此时整个树还没有连通，则需要补充 $(v-1,v+1)$ 这条边。
对于每个连通块，只需要考虑其内部点编号 $\min$ 向 $\min-1$ ，以及内部点编号 $\max$ 向 $\max+1$ 的边。这些边足够实现把 $[1,v-1]$ 和 $[v+1,n]$ 分别连通的目标。
这样每次需要考虑的边数是 $O(deg_v)$ 的，每次暴力做 Kruskal ，总复杂度也是 $O(n\log n)$ 的。
需要 DFS序 + ST 表辅助查询最小最大点编号，以及定位点所在连通块。总复杂度 $O(n\log n)$ 。
Codeforces Round 932 (Div. 2)