Codeforces Round 873 A~E

Codeforces Round 873 (Div.1）

A. Counting Orders

对于每个 \(a_i\)，可以计算出 \(c_i\) 表示有多少个 \(b_j\lt a_i\)。

那么第 \(i\) 个人就有 \(c_i\) 种可能的位置。

注意到如果将 \(a\) 升序排序，则能放的位置集合从前往后是包含的关系。

所以将 \(a\) 排序（等价于将 \(c\) 排序）后计算 \(\prod_{i=1}^{n}\max(0,c_i-i+1)\) 即可。

时间复杂度 \(O(n\log n)\)。

B2. Range Sorting(Hard Vision)

考虑研究一个序列的权值如何计算。

首先把 \(a\) 相同的再根据出现位置定义大小关系，这样就转成了 \(1\sim n\) 的排列：容易发现答案不变。

如果两个操作区间有交，不妨合并成一个，答案不会更差。

所以我们相当于是把原序列划分成若干段，每段进行一次排序操作。

可以看出权值就是 \(n-cnt\)，其中 \(cnt\) 是你划分的段数。

所以我们要让划分的段数尽可能的多；划分的条件是要保证每一段之间都是有序的。

换言之如果我们断开了 \(i\) 和 \(i+1\)，那么 \(\le i\) 的最大值要小于 \(\gt i\) 的最小值。

现在回到原问题来，我们实际上是要统计：每个子区间的分段次数和。

考虑一个 \(i \leftrightarrow (i+1)\) 的位置，有多少个子区间经过它且在此分段。

我们考虑从小往大激活 \(a\) 中的每个位置，则 \([L,R]\) 合法（\(L\le i\lt R\)）当且仅当有一个时刻我们激活了 \([L,i]\)，而 \((i,R]\) 全部没有被激活。

我们可以让 \([L,R]\) 在激活了 \([L,i]\) 最大值的那个时刻被统计到。

所以当我们本次激活 \(x\) 的时候，考虑其所在连通块 \([l,r]\)（\(l\le x\le r\)），则 \(L\) 的取值在 \([l,x]\) 范围；\(R\) 的取值在 \((r,p)\) 范围，其中 \(p\) 是 \(r\) 后面第一个已经被激活的位置。

求连通块 \([l,r]\) 可以用并查集维护，而寻找 \(p\) 可以用 std::set<int> 维护。时间复杂度 \(O(n\log n)\)。

C. Palindrome Partition

考虑如何判定一个串是否合法。

结论是我们贪心地划分就行。

如果我们不贪心地划分而仍然得到了解，则说明存在一对 \(p\lt q\) 满足长度为 \(p,q\) 的前缀都回文，假设 \(p\) 是最小的回文前缀。

当 \(2p\le q\) 的时候，注意到 \(s[q]\) 可以分成开头 \(p\) 个；结尾 \(p\) 个，中间长度为 \(q-2p\) 的一段；显然这三段都是回文的。

当 \(2p\gt q\) 的时候，\(s[q]\) 的前 \(p\) 个和后 \(p\) 个有交为 \(2p-q\) 的公共段；所以这一段是回文的，那么最开始的前 \(2p-q\) 个也是回文的；而 \(2p-q \lt p\)，所以这和 \(p\) 是最小回文前缀矛盾。

感觉不如.... Double Palindrome

回到原题：考虑设 \(f(i)\) 是最小的 \(j\) 满足 \([i,j]\) 是偶回文串，当求出了 \(f(i)\) 以后连 \(i\rightarrow f(i)+1\)，则题目所求等价于这张图上的路径条数（七点终点不同），这个很容易在 \(O(n)\) 的时间内 \(dp\) 出来。

然后考虑求 \(f(i)\)。考虑设 \(j\leftrightarrow (j+1)\) 为回文中心能拓展到的长度是 \(g(j)\)，则相当于求最小的 \(j\ge i\) 满足 \(j-g(j) \le i\)。

枚举 \(j\)，则相当于把 \([g(j),j]\) 这个区间内还没有确定 \(f\) 的位置，把他们的 \(f\) 全部设为 \(2\times (j-i)\)，这个过程容易用并查集维护。

时间复杂度 \(O(n\log n)\)，瓶颈在于用哈希 + 二分求 \(g(j)\)。当然使用 \(\text{manacher}\) 可以做到 \(O(n)\)。

D. Two Centroids

一棵树如果要有两个重心，首先它们必须相邻；然后考虑断掉他们之间的连边，两边的连通块大小必须完全一致。

这对树的形态做出了很强的约束。我们可以 \(O(n)\) 解决树形态固定的情况：枚举一个点 \(x\)，那么两个重心是 \(x,fa_x\) 的答案就应该是 \(|sz_x-(x-sz_n)|=|2sz_n-x|\)。

回到动态加叶子的情况，首先这个形式可以看成一颗确定的树，每次激活一个点。

这样利用 \(\text{bit}\) 可以做到 \(O(\log n)\) 求某个时刻的一个位置的子树大小 \(sz_x\)。

注意到二者必定有一个是树本身的重心，否则我们把它们同时往重心移动一步，小的连通块变大大的连通块变小且依旧满足小的连通块 \(\le\) 大的连通块，答案一定更优秀。

所以我们先考虑求出每个时刻的重心，这个很好做，我们加入一个叶子，那么原重心这个方向的连通块大小就增加了 \(1\)，如果它大于了一半就往这个方向移动一步就好了。

然后现在考虑问题变成了每次给一个点 \(u\) 问当前 \(u\) 的所有子树（无根树意义下）里 \(sz\) 最大的那个（显然这样加的点最少）。

考虑以 \(1\) 为根的话，父亲的那个部分是容易 \(O(\log)\) 直接算出的，关键是要找到它的重儿子是哪个。

考虑加入一个点 \(u\)，重儿子可能会更改的肯定是 \(1\rightarrow u\) 链上的某个点；且这条链上最多只有 \(O(\log n)\) 个点是父亲的轻儿子（根据轻重链剖分的理论），显然本来是重儿子的还会是重儿子，所以只用看这些轻儿子是否变成了新的重儿子即可，那么这个部分是单次 \(O(\log^2)\) 的，现在考虑如何去找这些点。

也就是抽象成：树上激活/熄灭一个单点，找到根链上的所有激活点。

如果是序列，则根链变成前缀，然后考虑可以维护 std::set<int> 并在其上二分查找；对于树上，我们树剖以后对 \(O(\log n)\) 个区间都做这样的事情，复杂度是均摊 \(O(\log^2 n)\) 的（每个激活点贡献 \(O(\log n)\) 的查找开销）。

这样时间复杂度 \(O(n\log^2 n)\)，可以预料到 \(5\times 10^5\) 是无法通过的，把 std::set<int> 改成树状数组上二分即可，这样常数小了非常多，在 \(1\) 秒内都可以通过。

当然，这并不是正解；我们 rewind 一下，回到求重心 \(u\) 的做法。

假设我们知道了加入新点之前的 \(u\) 和重儿子大小（包括父亲那部分也考虑在内），则考虑新点对应的那颗子树，如果我们的 \(u\) 没有变，那么考虑用它的大小更新重儿子大小；否则我们知道重儿子大小就是 \(\lfloor \frac{i}{2}\rfloor\)（\(i\) 是当前加入点的数目）。

所以只用一个 \(\text{bit}\) 和一次 \(\text{dfs}\) 其实就够了，时间复杂度 \(O(n\log n)\)。

E. Bus Routes

首先可以看出，我们只研究叶子和叶子之间的可达性。

然后考虑把 \(n=2\) 的特判掉，当 \(n\ge 3\) 的时候总能找到一个非叶子点 \(r\)，以 \(r\) 重新定根。

考虑两个叶子 \(u,v\) ，要么有一条路径 \(u\leftrightarrow v\)，要么必须中转一次。无论如何 \(lca\) 处都会被经过到。

所以考虑枚举 \(lca\)，然后考虑所有 \(lca(u,v)=p\) 的叶子点对 \((u,v)\)。

如果两个人为起点都存在一条路径经过 \(p\)，显然它们可以中转到一起；如果都不存在显然无法中转到一起；如果只有一个人的路径能经过 \(p\)，则相当于是这样一个形态：\(u\) 经过 \(lca\) 然后向下往 \(v\) 走，\(v\) 的路径向上够；最后两人回合。

发现第一种情况可以视为第三种情况的特例。

因此，我们对每个叶子找到最浅的 \(u\) 满足叶子到 \(u\) 有一条路径，问题变成了查询是否 \(u\) 子树外的叶子到 \(u\) 都有一条路径。

可以先对每个叶子找到这个 \(u\)，然后统一处理询问。

考虑用叶子去覆盖这些询问点，则一个考虑叶子 \(u\) 的一条路径 \(u\rightarrow v\)，它需要覆盖到 \(u\rightarrow v\) 的路径上所有不是 \(u\) 祖先的点。

考虑树剖：首先 \(u\rightarrow r\) 的路径被剖分成了 \(O(\log n)\) 段，所以不在这条路径上的点集也被剖分成了 \(O(\log n)\) 段，记作 \(P\)；每条从 \(u\) 出发的路径根据树剖划分成 \(O(\log n)\) 段，把他们合并成若干个不交的区间，然后分别给 \(P\) 集合的每一段做贡献。贡献是区间加所以打差分就好了。

时间复杂度 \(O((n+m)\log^2 n)\)，因为没有用数据结构所以常数不大，可以通过。

F.Copium Permutation

我还没有想出来。

可能想不出来了。