Open Cup 还是一场场做比较有感觉。
A
简要题意.
维护两个二元组集合 \(U,V\)，支持 \(Q\) 次在某个集合中插入或删除二元组，查询 \[ \min \{\max\{u_x+v_x, u_y+v_y\}\mid (u_x, u_y) \in U, (v_x, v_y) \in V\} \]
\(Q,u_x,u_y,v_x,v_y \le 2.5\times 10^5\)。
没什么好几何意义，直接拆 \(\max\)，考虑 \(u_x-u_y \le v_y-v_x\) 时取 \(u_x+v_x\)，否则取 \(u_y+v_y\)。
我们以 \(u_x-u_y\) 为下标存储 \(U\) 中的点，以 \(v_y-v_x\) 存储 \(V\) 中的点，这样只需维护左边的 \(u_x\) 加右边的 \(v_x\)，或者左边的 \(v_y\) 加右边的 \(u_y\)。一棵线段树维护这个分治信息即可。
B
简要题意.
给定 \(n,k\)，构造有 \(k\) 个 \(1\)，\(n^2-k\) 个 \(0\) 的 \(n\times n\) \(01\) 矩阵使得不存在一行、一列、或者两条对角线之一全是 \(1\)，或报告无解。
\(n \le 100\)。
显然我们只要构造一个最大的 \(k\) 就可以解决这题。一个上界是 \(n^2-n\)，但这紧吗？
\(n\) 是奇数的时候，只需要挖掉一条对角线。
再玩一玩，\(n\) 是偶数的时候，可以交换第一行和最后一行。
好像要特判 \(n=2\)。
C
简要题意.
给定 \(N\) 和序列 \(A_0, A_1, \dots, A_{2^N-1}\)，找到任意一对 \(0 \le i, j < 2^N\) 使得 \(A_i + A_j < A_{i \operatorname{bitand} j} + A_{i \operatorname{bitor} j}\)。
\(N \le 20\)。
考虑枚举集合 \(S_1, S_2, S_3 \subseteq \{0, 1, \dots, N-1\}\)，要求 \(S_1 \cap S_2 = S_2 \cap S_3 = S_3 \cap S_1 = \varnothing\)。
于是要求 \[
A(S_1 \cup S_3) + A(S_2 \cup S_3) < A(S_3) + A(S_1 \cup S_2 \cup S_3)
\]
移项，有 \[ A(S_2 \cup S_3) - A(S_1 \cup S_2 \cup S_3) < A(S_3) - A(S_1 \cup S_3) \]
令 \(F(S) = A(S \cup S_3) - A(S_1 \cup S \cup S_3)\)，则我们要求存在 \(S\) 使得 \(F(S) < F(\varnothing)\)。
假设存在这样一个 \(S\)，令 \(k = |S|\)，定义 \(S_{1,\dots,i}\) 表示 \(S\) 的前 \(i\) 个元素构成的集合。
则我们一定能找到一个 \(i\) 使得 \(F(S_i) < F(S_{i-1})\)（否则 \(F(S) = F(S_k) \ge F(\varnothing)\)），也就是说 \[
A(S_i \cup S_3) - A(S_1 \cup S_i \cup S_3) < A(S_{i-1} \cup S_3) - A(S_1 \cup S_{i-1} \cup S_3)
\]
我们把 \(S_{i-1}\) 和 \(S_3\) 并起来，就证明了 \(S_2\) 只需要取大小为 \(1\) 的集合。
类似地，\(S_1\) 也只需要大小为 \(1\) 的集合。
暴力即可。时间复杂度 \(O(N^2 2^N)\)。
D
简要题意.
给定 \(N\) 和一个排列 \(A_1, A_2, \dots, A_N\)。一开始所有元素都未被摧毁。
每个时刻你可以在排列左侧同时发射两颗高度分别为 \(H_1, H_2\) 的子弹。这会分别摧毁从左往右第一个未被摧毁的 \(\ge H_1\) 和 \(\ge H_2\) 的元素。
如果这两个元素是同一个，也只会摧毁一个。
求最少需要多少时刻可以摧毁所有元素，并给出一组方案。\(N \le 10^5\)。
牛逼论文题，但或许也可以猜。
建图，对于逆序对 \(i < j, A_i > A_j\) 连边 \(i \to j\)。这也叫做排列图（Permutation Graph）。则每次就是删去最多两个入度为 \(0\) 的点。
对于任意 DAG，有论文给出了这样一个方法：
- 首先，找到一个特殊的拓扑序。像一般的拓扑排序那样，每次删去一个入度为 \(0\) 的点并加到拓扑序中。
但此处，如果有多个入度为 \(0\) 的点，设 \(N(v)\) 为 \(v\) 的入边被删除的时间的集合。我们将每个 \(N(v)\) 中的元素降序排列后寻找字典序最小的 \(N(v)\)（换句话说，尽可能早地被减小入度的 \(v\)），并在这一轮中选择 \(v\)。 - 然后，逆着拓扑序反着求答案。每次取两个在拓扑序中最靠后的，出度为 \(0\) 的点删去，并加到答案的前端。
这样我们就至少获得了一个多项式时间的做法。考虑在排列图上如何优化之。
首先，计算出 \(level(i)\) 表示以 \(i\) 结尾的最长路。也就是以 \(i\) 结尾的最长下降子序列长度。
我们按照 \(level(i)\) 升序处理所有点，不难发现这样和拓扑排序是等价的，且同层间没有连边。
那么，分层做，我们只需要支持对任意 \(v,w\) 比较 \(N(v),N(w)\) 的字典序即可。由于已经降序，所以我们事实上只需要比较 \(N(v)-N(w),N(w)-N(v)\) 中的最大值。
这是单点修改，矩形 \(\max\)，用树套树即可做到单次 \(O(\log^2 n)\)，总共 \(O(n\log^3 n)\)。
还是有点慢，但我们发现如果我们需要先求这个 3-side 矩形中点的最大 \(level(i)\)（这是静态的），是可以用主席树 \(O(n\log n)\) 预处理 \(O(\log n)\) 查询的（不过原论文好像用的是划分树状物，可能这就是学术界做法吧）。
而同 \(level\) 的点一定是反链，所以可以转化为区间 \(\max\) 查询。
这样就做到了 \(O(n\log^2 n)\)。
但是这似乎还是太 naive。
（似乎）可以观察到最小时间等于 \(N\) 减去补图的最大匹配。进一步，有论文证明了本题的答案和补图的最大匹配是双射（具体的映射应该很好猜），那么我们对于一组最大匹配只需要一直找入度为 \(0\) 的点就可以排出一个操作顺序。这是 \(O(n\log n)\) 的。
而目前有论文声称可以在 \(O(n\log \log n)\) 时间内计算排列图（显然排列图的补图也是排列图）的最大匹配，感觉很 nb。
E
简要题意.
对于给定的区间列 \([s_1, e_1], [s_2, e_2], \dots, [s_N, e_N]\)，定义区间图是无向图 \((V,E)\)，其中 \(V = \{1, 2, \dots, N\}\)，\(E = \{(i, j) \mid [s_i, e_i] \cap [s_j, e_j] \ne \varnothing\}\)。
给定 \(N, K\) 和 \(N\) 个区间 \([s_i, e_i]\)，每个区间有权值 \(w_i\)，要求删除若干区间使得剩下的区间构成的区间图的各连通块大小不超过 \(K\)。
问删除的区间的最小权值和。\(K \le N \le 2500\)，\(e_i \le 10^9\)，\(1 \le w_i \le 10^9\)。
区间图的一个连通块一定可以表为一个区间。
反过来，可以发现我们只需要将整个数轴划分为若干区间，在各区间中选择包含在其中的前 \(K\) 大个区间即可。不难发现这样一定可以计算出答案。
于是，要想将计算转移代价的过程优化到 \(O(N^2 \log N)\) 或 \(O(N^2)\) 是很容易的。
F
简要题意.
给定二维平面上 \(N\) 个矩形，有 \(M\) 次移动操作，每个移动操作是给定 \(d\)，将某个矩形移动 \(\{-d,0,d\}^2 \setminus \{(0,0)\}\) 八种方向之一。
移动时会留下轨迹，即留下 \(d\) 个矩形。 接下来 \(Q\) 次询问某个点被多少个矩形覆盖。\(N,M,Q,x,y \le 2.5 \times 10^5\)。
差分，转化为水平射线、垂直射线、和 \(x\) 轴成 \(45^\circ\) 或 \(135^\circ\) 的射线加，矩形查询。
容易转化为二维偏序。
G [Not to be continued]
简要题意.
给定 \(N\) 点 \(M\) 边无向图，对于每条边求出删除这条边后有多少个点满足删除其之后图不再连通。
\(N \le 2.5\times 10^5\)，\(M \le 10^6\)。
先特判割边，这个时候除非有一边只有一个点，答案为 \(N\)。
将边拆点，可以认为是我们需要找出一类两个点的割。所以，这是个三连通性问题。
算了。不是很想补这题。
不过好像有大手子直接用 SPQR 树过了，，
H
简要题意.
有数轴上的 \(N\) 条线段 \(L_i, R_i\)，保证 \(i\) 递增时长度不降，且没有相同的区间。
初始时，数轴上没有任何地方被覆盖。每次选择区间内未被覆盖的长度最小的一个区间（若相等则取编号最小的），将区间内覆盖。
求出覆盖的顺序。\(N \le 2.5 \times 10^5\)，\(R_i \le 10^9\)。
显然，包含的区间一定在初始时和答案中都有序，因此我们只需考虑当前可选的区间中不包含其他区间的那些。
这就有 \(L, R\) 各自上升，因此很容易维护。
我们还要支持取出新的不包含其他区间的区间，也就是说，不存在 \(L_j, R_j\) 使得 \(L_i \ge L_j, R_j \le R_i\)。若将其看成二维点 \((L_i, R_i)\)，则即右下角没有点。
适当排序后就是前 / 后缀最值，容易维护。
（其实 D 题也有这个东西）
I
简要题意.
给定 \(N\) 和长为 \(N\) 的序列 \(A_1, A_2, \dots, A_N\)，有依次执行的 \(Q\) 次单点修改。
在所有修改前和每次修改后，需要输出 \(|\{(i,j)\mid A_i = A_j \land (i < k < j \implies A_k < A_i)\}|\)。\(N \le 10^5\)，\(Q \le 2.5\times 10^5\)。
显然地，所有数对可以构成一棵树。
按时间分治，设当前在处理 \([s,e]\) 内的修改，我们注意到每个修改会导致树上一条祖先后代链的数对被删除。
假设每次是从一个点 \(v\) 往上删到一点 \(u\)，我们不妨将所有 \(u\) 的父亲和所有 \(v\) 拿出来建出虚树，其余的边都可以扔掉。
途中需要用线段树来维护新增的数对。
直接实现就是 \(O((N+Q)\log^2(N+Q))\) 的。
然而事实上并不需要显式建树，注意到可以用单调栈来在按 DFS 序遍历的时候（也就是按左端点升序遍历）维护每个点的所有祖先。
可能会好写一点（大概）。
另，zkw 线段树在这题上很有用。
J [Not to be continued]
简要题意.
给定 \(N\) 点 \(M\) 边的森林，执行 \(Q\) 次下述操作之一：
- 连接一条边。保证仍是森林。
- 断开一条边。
- 查询某个连通块中所有直径两两公共点个数之和。
\(N,Q \le 10^5\)。
考虑只有一次询问怎么做：将直径中点提到根，然后 DP 即可。
然后上 Top Tree 即可 \(O(n + q\log n)\) 解决此题……
K
简要题意.
给定 \(N\) 个点的树，各点有点权 \(A_i\)。
给定参数 \(L,R\) 和 \(K\)，你需要对于所有 \(0 \le i \le K\) 的 \(i\) 判断是否存在割掉 \(i\) 条边的方案使得各连通块点权和在 \([L, R]\) 内。\(K < N \le 10^3\)，\(K \le 50\)，\(A_i, R \le 10^{18}\)。
设 \(f(u,k,s)\) 表示使得以 \(u\) 为根的子树内是否存在一种方案已经确定 \(k\) 个连通块，剩下一个未确定的连通块点权和为 \(s\)。
暴力实现是 \(O(NKR^2)\) 的。
令 \(S(u,k) = \{s\mid f(u,k,s)\}\)，注意到 \(\max S(u,k) - \min S(u, k) \le k(R-L)\)。
然后，可以归纳证明，我们只需对于每个 \([\min S(u, k) + i(R-L)+1, \min S(u, k) + (i+1) (R-L)]\) 的区间中保留最小和最大值即可。
时间复杂度 \(O(NK^3)\)。
具体证明可以参考官方题解或者 pjudge。
L
简要题意.
给定一个 \(H\times W\) 的矩阵，每个位置有以下四种管道之一：
或是空位。空位包括必填项、禁填项和没有限制的空位（这些限制仅针对于玩家）。
你作为玩家，需要用以上四种管道填上尽量多的空位，使得管理员存在一种方案用以下的管道填满剩下的空位使得：
- 每个格子都有管道。
- 没有死胡同。
- 不能走到矩阵外部。
\(H,W \le 100\)。
你看这限制含糊不清的，大胆猜测只需要我们填上的管道不矛盾即可。
考虑同一行的相邻两个已经存在的管道，我们容易判断其中间是否能恰好填满，或是缺一个。
同一列的类似。
因为我们希望缺的尽量少，所以我们把这些交错的缺管道的行列连边，做二分图匹配即可。