Day 1, T1. 卡牌游戏

题意：有 $n$ 张牌，第 $i$ 张牌正面写着数字 $a_i$ ，背面写着数字 $b_i$ ，初始时正面向上。请你选择 $m$ 张牌翻面，使翻面后所有朝上的数字极差（最大值减最小值）最小。

$m<n\le10^6$ ， $1\le a_i,b_i\le10^9$ ，保证所有 $a_i,b_i$ 互不相同， $a_i<a_{i+1}$ 。

答案一定是翻牌的一个前缀和一个后缀，即牌 $1\sim l$ 为背面， $l+1\sim r-1$ 为正面， $r\sim n$ 为背面。

而且，最优解时一定不会出现 $i\in[1,l],a_i>b_i$ 。同理也不会有 $i\in[r,n],a_i<b_i$ 。这是因为翻前缀是要使最小值增大，翻后缀是要使最小值减小。

后面做法比较乱搞，也不会证明正确性。

枚举了 $r$ 单增时，发现 $l$ 也是单增的。具体策略是只要 $a_l<\min_{i=r}^n\{b_i\}$ ，则当前的 $l$ 取到最小值，必须 $+1$ 。

这样会漏过一些解。再枚举 $l$ 单减， $r$ 同理也单减。所以像上面一样只要 $a_r>\max_{i=1}^l\{b_i\}$ 就让 $r-1$ 。

用所有移动过程中的 $l,r$ 更新答案就正确了，并且通过了 UOJ 的所有 Hack 数据。正确性只会感性理解。

需要维护的东西只有 $b$ 序列的前后缀 $\min,\max$ ，中间 $a$ 的 $\min,\max$ 显然在两端。所以时间复杂度 $O(n)$ 。

Day 1, T2. 矩阵游戏

题意：给你一个 $(n-1)\times(m-1)$ 的矩阵 $b_{i,j}$ ，请你构造一个 $n\times m$ 的矩阵 $a_{i,j}$ ，满足：

$0\le a_{i,j}\le10^6$ 。

$b_{i,j}=a_{i,j}+a_{i,j+1}+a_{i+1,j}+a_{i+1,j+1}$ 。

输出任意方案，或判断无解。多组数据。

$n,m\le300$ ， $T\le10$ 。

构造一个只满足条件二的矩阵 $a$ 是容易的，考虑如何调整将现在这个矩阵 $a$ 使它满足条件一。调整时需要满足保持 $a$ 满足条件二。

由于条件二每个限制都是 $2\times2$ 的小矩形，可以考虑将同一行 / 列的元素交错 $\pm x$ 。设第 $i$ 行元素的 $x=c_i$ ，第 $i$ 列元素的 $x=d_i$ 。

为满足不等式，建立差分约束系统。但可能存在这种情况：

\begin{bmatrix} +c_1+d_1&-c_1+d_2&\cdots\\ +c_2-d_1&-c_2-d_2&\cdots\\ \vdots&\vdots&\ddots \end{bmatrix}

差分约束时就出现了 $0\le a_{i,j}+c_i+d_j\le10^6$ 这种东西，不方便处理。

可以再交错一下变成：

\begin{bmatrix} +c_1-d_1&-c_1+d_2&\cdots\\ -c_2+d_1&+c_2-d_2&\cdots\\ \vdots&\vdots&\ddots \end{bmatrix}

使得每个位置都出现了减号。

用 SPFA 跑最短路，出现负环则说明无解。时间复杂度 $O(nm(n+m))$ 。

Day 1, T3. 图函数

题意：给你一张有向图 $G$ ，定义函数 $f(u,G)$ ：

初始 $\text{cnt}=0$ ，图 $G'=G$ 。

从 $1$ 到 $n$ 枚举点 $v$ 。若 $G'$ 中 $u\rightarrow v$ 的路径和 $v\rightarrow u$ 的路径都存在，则将 $\text{cnt}+1$ 并在 $G'$ 中删除点 $v$ 及其所有连边。

结束时 $\text{cnt}$ 即为函数值。

定义 $h(G)=\sum_{u\in V}f(u,G)$ 。现给出 $G$ ，请你分别求出 $h(G)$ ，和删除第 $i$ 条边后的 $h(G_i)$ 。

$n\le1000$ ， $m\le2\times10^5$ ，保证无重边自环。

观察性质，对 $f(u,G)$ 的值有贡献的点 $v$ 肯定满足 $v\le u$ ，因为当 $v=u$ 时 $u$ 会从图中删去。

删除操作难以实现。转化 $u\rightarrow v$ 的路径和 $v\rightarrow u$ 的路径都存在的条件，发现实际上是问 $u\rightarrow v$ 和 $v\rightarrow u$ 是否能不经过 $1\sim v-1$ 中的点。因为一旦经过了 $1\sim v-1$ 中的点 $x$ ，会使得 $x$ 存在 $u\rightarrow x$ 和 $x\rightarrow u$ 的路径，则 $x$ 一定会在 $v$ 之前被删去。

每个点对的贡献肯定是 $h(G_i)$ 的一个前缀。可以求一下每个点对最晚贡献时间。

只走 $v\sim n$ 中的点显然 Floyd。改一下传递闭包的写法，求一下最晚联通时间即可。

时间复杂度 $O(n^3)$ 。足以通过了。

PS：STL 里的 min / max 是真的慢，改成手写才能过。

Day 2, T1. 宝石

题意：给你一棵 $n$ 个点的树，每个点上有第 $w_i$ 种宝石，宝石共 $m$ 种。 $q$ 次询问，每次询问从 $u_i$ 出发沿最短路径到达 $v_i$ ，途中按 $P_1,P_2,\cdots P_c$ 的顺序收集宝石，即初始时定义变量 $\text{cnt}=0$ ，对于途中的一个城市 $x$ （包括 $u_i,v_i$ ），若 $w_x=P_{\text{cnt}+1}$ ，则将 $\text{cnt}+1$ ，求最后的 $\text{cnt}$ 。

注意询问的 $P$ 序列是相同的。

$n,q\le2\times10^5$ ， $w_i,c\le m\le5\times10^4$ 。保证所有 $P_i$ 互不相同。

先考虑上行路径。采用倍增，我们希望从离出发点最近的拥有 $P_1$ 的祖先开始，向上跳到最大的合法 $\text{cnt}$ 。

先定义一个 $t_{P_i}=i$ 。记 $f(i,k)$ 表示 $i$ 和 $i$ 的祖先中离 $i$ 最近的能跳到的拥有宝石 $P_{t_{w_i}+2^k}$ 的节点， $g(i)$ 表示 $i$ 和 $i$ 的祖先中离 $i$ 最近的拥有宝石 $P_1$ 的节点。所谓『能跳到』，是指 $i\sim j$ 中间必须出现 $P_{t_{w_i}}\sim P_{t_{w_j}}$ 的所有宝石。

下行路径总是不好处理。考虑二分当前询问的答案 $K$ ，上下行路径就变得类似了。

注意下行路径中有一个查询 $i$ 和 $i$ 的祖先中离 $i$ 最近的能跳到的拥有宝石 $P_K$ 的节点的操作，这个可以主席树，相当于 $i$ 到根路径上深度最大的 $w_j=P_K$ 的点 $j$ 。所以上行路径的 $g(i)$ 显然也可以直接用这个主席树解决。

时间复杂度大概是 $O(n\log n+q\log^2m)$ 。这个算法是在线的。

Day 2, T2. 滚榜

$f(S,x,y)$ 表示 $S$ 中队伍已上榜，最后一个上榜的队伍是 $x$ ，且最多还剩 $y$ 道题目可分配的方案数。

f(S,x,y)=\sum_{i\in S\land i\ne x}f(S-\{i\},i,y-(n-x+1)\cdot\max\{a_i-a_x+[i>x],0\})

时间复杂度 $O(2^nn^2m)$ 。

Day 2, T3. 支配

题意：给你一张 $n$ 个点 $m$ 条边的有向图， $q$ 次询问，每次询问加入边 $(u,v)$ 后受支配集改变的点的个数。询问独立。

$n\le3000$ ， $m\le2n$ ， $q\le2\times10^4$ ，保证 $1$ 出发能到达所有点，图中无重边自环。

支配树可以暴力 $O(n^2)$ 地建出，即枚举删除每一个点 $u$ ，从 $1$ 出发无法到达的点被 $u$ 支配。

结论 1：加入边 $(u,v)$ 后， $x$ 的受支配集改变，当且仅当 $x$ 在支配树上的父亲 $\text{fa}_x$ 的受支配集改变，或 $\text{fa}_x$ 不再支配 $x$ 。

结论 2：加入边 $(u,v)$ 后， $\text{fa}_x$ 不再支配 $x$ ，当且仅当原图上删除点 $\text{fa}_x$ 后， $1$ 能到 $u$ 且 $v$ 能到 $x$ 。

至此已有做法。在原图上预处理出 $f(i,j)$ 表示删除 $\text{fa}_i$ 后 $1$ 能否到达 $j$ ，以及 $g(i,j)$ 表示删除 $\text{fa}_i$ 后 $j$ 能否到达 $i$ 。每次询问枚举所有点 $x$ ，检查 $\text{fa}_x$ 是否不再支配 $x$ ；若不再支配，则其对答案的贡献为 $x$ 在支配树上的子树大小。