2022-02-28~

CF1647E¶

题意¶

$n$ 个位置，初始第 $i$ 个人的编号是 $b_i$，$b_1,b_2,\ldots,b_n$ 是一个 $1$ 到 $n$ 的排列。门外依次站着编号为 $n+1,n+2,\ldots$ 的人。

一次换座位的过程如下：

第 $i$ 个位置上的人去第 $p_i$ 个位置，如果有多个人去同一个位置，编号小的留下，其它人永久删除。此时会有一些位置为空，则门外的人依次进来，从小到大占据每个位置。

现在给定进行了一定次数 (可能为 $0$) 换座位后每个位置上人的编号 $a_1,a_2,\ldots,a_n$，求合法的字典序最小的 $b_1,b_2,\ldots,b_n$，保证存在解。

保证至少有两个 $p_i$ 相同。

($1 \le n \le 10^5$，$1 \leq a_i \leq 10^9$)

题解¶

如果 $a_1,a_2,\ldots,a_n$ 是 $1$ 到 $n$ 的排列，则没有进行换座位，直接输出即可。

否则，每次空出的数量是相同。找到 $a_1,a_2,\ldots,a_n$ 中的最大值，找到以其为结尾每次增加 $1$ 的最长子序列，长度即为空位数量，这样就可以算出进行了几轮。假设进行了 $k$ 轮。

利用倍增求出每个位置进行 $k$ 次换座位后到哪个位置 (只看这个人，不管删除的问题)，设第 $i$ 个位置到 $f_i$。

对于 $a_1,a_2,\ldots,a_n$ 中所有 $\le n$ 的数的位置 $i$，存在恰好一个 $k \in \{j \mid f_j=i\}$ 使得 $b_k=a_i$，且对 $j \in \{j \mid f_j=i, j \ne k\}$ 均有 $b_j > a_i$，否则最终 $a_i$ 就会更小。因此令最小的 $j$ 使得 $b_j=a_i$ 是最优的。同时对于不同的 $i$，$\{j \mid f_j=i\}$ 互不相交，因此这样贪心可以确保 $a$ 中这些位置都会出现。

对于 $b$ 中没有确定的位置 $i$，若 $a_{f_i} > n$ 则这个位置放什么都行，否则需要保证这个位置上的数 $> a_{f_i}$，否则最终 $a_{f_i}$ 就是这个数了。从小到大遍历 $i$，用一个 set 维护，贪心地选最小的符合条件的值，容易发现这样在满足字典序最小的前提下也尽可能让解存在，因为原题保证解存在，所以是对的。

注意到，确定 $b$ 中没有确定的位置时，无论结果如何，$a$ 中 $>n$ 的数最终都一定会正确出现。这是因为原题保证有解，而 $>n$ 的数碰到 $\le n$ 的数一定会被删除，因此怎么安排都不会对其产生影响。

CF1648D¶

题意¶

$3 \times n$ 的矩阵，每个位置的权值为 $a_{i,j}$，从 $(1,1)$ 到 $(3,n)$，每次只能向右向下走，获得的权值是所有经过位置的权值之和。第二行初始所有位置都被封锁，有 $q$ 种可选方案，第 $i$ 种方案可以解锁第二行的区间 $[l_i,r_i]$，并花费 $k_i$ 价值，同一个位置可以被解锁多次，一个位置只有被解锁才能经过。总收益为「获得的权值 $-$ 解锁所花费的价值」，最大化总收益。($1 \le n,q \le 5 \times 10^5$)

题解¶

设 $\displaystyle s_{i,j}=\sum_{k=1}^ja_{i,j}$。

设 $f_{i}$ 为从 $(1,1)$ 到 $(2,i)$ 且 $i$ 是某个区间的右端点的最大收益，按每个区间的右端点从小到大排序后，对于区间 $[l,r]$ 有如下转移： $$ \begin{aligned} &f_i \gets \max_{j=l-1}^{i-1} (f_{j} + s_{2,i}-s_{2,j}) - k \ &f_i \gets \max_{j=l}^{i} (s_{1,j}-s_{2,j-1}+s_{2,i}) - k \end{aligned} $$ 分别为从上一个已经解锁的区间过来，以及当前区间是一个解锁的区间。

可以维护两个单点修改区间查询最大值的线段树维护。

接着枚举第二行中最后经过的解锁区间 $[l,r]$，若由上一个已经解锁的区间过来，答案为： $$ \max_{l-1 \le i \le j \le r} (f_i-s_{2,i}+s_{2,j}+s_{3,n}-s_{3,j-1})-k $$ 若这是唯一一个解锁的区间，答案为： $$ \max_{l \le i \le j \le r} (s_{1,i}-s_{2,i-1}+s_{2,j}+s_{3,n}-s_{3,j-1})-k $$ 上述两种情况均可以归纳为求解 $\displaystyle \max_{l \le i \le j \le r}(A_i+B_j)$，这可以用线段树维护三个值来解决：

左区间 $\max A_i$
右区间 $\max B_i$
全局 $\displaystyle \max_{l \le i \le j \le r}(A_i+B_j)$

总时间复杂度为 $O((n+q) \log n)$，三个线段树常数很大。

CF1648E¶

题意¶

给定 $n$ 个点 $m$ 条边的带权无向连通图，一条路径的长度是这条路径上每条边权值的最大值。考虑这个图的补图，令每条边的权值为其在原图上的最短路，保证补图连通。求原图上每条边两个端点在补图上的最短路 (定义同上)。($1 \le n,m \le 2 \times 10^5$)

题解¶

对原图求 Kruskal 重构树，两点 LCA 的权值即为它们之间的最短路。这样就得到了补图中每条边的边权，再求出补图的 Kruskal 重构树，问题就解决了。

但补图的边数是 $O\left(n^2\right)$ 的，需要考虑如何快速求解。考虑对补图做 Kruskal 算法，利用特殊性质只考虑很少的边。

原图求 Kruskal 重构树的过程，即原图求最小生成树的过程，每连一条边，就考虑所有补图中权值等于这条边的那些边，那么这样考虑的补图中边的权值是从小到大的，符合 Kruskal 算法的过程。

每连一条边，原图中的两个连通块就会合并，这两个连通块中的点在补图中肯定也没有连向该连通块之外的边 (因为还没考虑)，因此可以将它们进行合并。暴力枚举两两连通块中的每组点，若是原图中的边则不能合并，否则可以合并，因为原图只有 $m$ 条边，这样均摊的复杂度是正确的。

具体实现过程，用 set 存原图中的 $m$ 条边，则遍历时合并失败部分的复杂度是 $O(m \log m)$ 的。使用 vector 存补图中每个连通块中的点，启发式合并，这部分复杂度为 $O(n \log n)$。

最麻烦的部分是记录原图中每个连通块中补图中的连通块，用 set 记录每个连通块中补图连通块的并查集根节点编号，合并时暴力遍历一个 set，不断和另一个 set 中的点合并，最后将无法合并的连通块并查集根结点编号再放入一个 set 中。

更详细一点，for 第一个 set，对每个根节点 $i$：

for 第二个 set，对每个根节点 $j$，把所有和 $i$ 合并成功的 $j$ 从第二个 set 移除，全部合并完后再把合并的根节点编号再放入第二个 set。如果合并成功则将 $i$ 从第一个 set 中移除，否则不移除。

最后将两个 set 中的点放入一个新的 set 中。

这部分怎么做复杂度都是对的，因为一共只会成功合并 $n-1$ 次、失败合并 $m$ 次，因为总复杂度是 $O((n+m)\log n)$。

上述 Kruskal 算法的过程中同时建出 Kruskal 重构树，倍增查询即可。

CF1651F¶

题意¶

$n$ 个防御塔，每个防御塔每秒都会恢复生命，假设第 $i$ 个防御塔前一秒生命值为 $x$，则下一秒生命值就会变为 $\min(x+r_i,c_i)$。初始第 $i$ 个防御塔血量为 $c_i$。

有 $q$ 个怪物，第 $i$ 个怪物会在第 $t_i$ 秒出现在第一个防御塔，之后它会每秒向后移动一个防御塔。怪物的初始生命之为 $h_i$，当它遇到一个防御塔，设该防御塔生命值为 $a$，怪物生命值为 $b$，则两者生命值同时减少 $\min(a,b)$。设第 $i$ 个怪物经过 $n$ 个防御塔后生命值为 $h'_i$，求 $\displaystyle \sum _{i=1}^q h'_i$。

保证 $t_i$ 严格递增。

($1 \le n \le 2 \times 10^5$，$0 \le t_i \le 2 \times 10^5$)

题解¶

考虑一个怪物会将一个前缀的防御塔生命值变为 $0$，然后将这个前缀之后的一个防御塔进行一定量的伤害 (有可能没有)，初次之外防御塔的状态都不会发生变化，考虑维护一个栈，里面两种由互不相交的区间组成：

区间 $[l,r]$ 内的防御塔被出发时间为 $t$ 的怪物经过时生命值变为 $0$，那么对于一个出发时间为 $t'$ ($t'>t$) 的怪物经过这个防御塔时，该防御塔恢复生命值的时间为 $t'-t$。
区间 $[l,r]$ 满足 $l=r$，被出发时间为 $t$ 的怪物经过时生命值变为 $x$ ($x>0$)。

且这些区间的并集即为 $[1,n]$。

一个怪物会新增 $O(1)$ 个区间，且一个区间至多被删掉一次，初始可以认为有 $O(n)$ 个长度为 $1$ 的区间，因此总区间数量是 $O(q+n)$ 的。

对于每个怪物，从前往后遍历每个区间，若为上述第二种区间，因为只有一个防御塔，直接判断即可；若为第一种区间，需要快速求出它在经过哪个前缀后生命值会变为 $0$，这可以在可持久化线段树上二分完成。具体来说，维护 $2\times10^5$ 个版本，第 $i$ 个版本维护区间 $[l,r]$ 的值 $a_{l,r,i}=\displaystyle \sum_{j=l}^r \left[\left\lceil\frac{c_j}{r_j}\right\rceil<i\right]r_j$ 和 $b_{l,r,i}=\displaystyle \sum_{j=l}^r \left[\left\lceil\frac{c_j}{r_j}\right\rceil\ge i\right]c_j$。栈中第一种区间所有防御塔在被这个怪物经过时恢复生命的时间是相同的，设为 $t$，那么区间 $[l,r]$ 的防御塔生命值即为 $a_{l,r,t}t+b_{l,r,t}$，在对应版本的线段树上二分即可，总时间复杂度为 $O((q+n)\log n)$。

CF1654F¶

题意¶

给定字符串 $s_0s_1\ldots s_{2^n-1}$，设 $f(i)=s_{0\oplus i}s_{1\oplus i}\ldots s_{\left(2^n-1\right)\oplus i}$，对 $i=0,1,\ldots,2^n-1$，求字典序最小的 $f(i)$ 并输出。($1 \le n \le 18$)

题解¶

类似后缀数组的思路，设仅考虑长度为 $2^i$ 的前缀：

$\text{sa}_{i,j}$ 满足对所有 $0 \le x < y < 2^n$ 有 $f(\text{sa}_{i,x}) \le f(\text{sa}_{i,y})$。
$\text{rk}_{i,j}$ 满足对所有 $0 \le x, y < 2^n$ 有 $f(x) < f(y) \Longleftrightarrow \text{rk}_{i,x} < \text{rk}_{i,y}$。

显然 $\text{rk}_{0,i}=s_i$ 满足条件，对于 $i=1,2,\ldots,n$，设 $g_{i,j} =(\text{rk}_{i-1,j},\text{rk}_{i-1,j \oplus 2^{i-1}})$，以其作为 $j$ 的权值进行排序就可以得到 $\text{sa}_{i,j}$，之后由 $\text{sa}_{i,j}$ 就可以得到 $\text{rk}_{i,j}$。

需要注意的是，不能直接令 $\text{rk}_{i,\text{sa}_{i,j}}=j$，而是先 unique 一波，令所有 $g_{i,j}$ 相同的 $j$ 具有同样的 $\text{rk}_{i,j}$。

最后输出 $f\left(\text{sa}_{n,0}\right)$ 即可。用 sort 代码短，复杂度为 $O\left(n^2 2^n\right)$，和后缀数组类似将排序改为基数排序就可以将复杂度降低到 $O\left(n2^n\right)$，可以但没必要。