Codeforces Round #539 (Div. 1)

有史以来打的最烂的一场...B题都WA了两发，D题数树不知道结论不会做，E题没调出来...GG了。

也说明我实力其实还不够吧...再多加练习，我还有机会继续努力。

A. Sasha and a Bit of Relax

题意：给定一个长度为 $n$ 的序列 $a$ ，求有多少个长度为偶数的区间满足区间前一半数的异或和等于后一半数的异或和。 $n \leq 3 * 10^{5}, a_{i} \leq 2^{20}$ 。

题解：考虑前一半数的异或和等于后一半数的异或和等价于整体异或和为 $0$ ，那么只需要做异或前缀和，统计位置的奇偶性相同的前缀和中，值相同的对数即可。复杂度 $O (n)$ 。

B. Sasha and One More Name

题意：给定一个回文串 $s$ ，你要将其分割 $k$ 次（划分为 $k + 1$ 段）并重新排列，将其变成一个与原来不同的回文串。求 $k$ 的最小值，无解则输出 $- 1$ 。 $| s | \leq 5000$ 。

题解：先考虑无解的情况，对于偶回文，全部相同则无解；对于奇回文，除中间的字符外全部相同则无解。考虑另外的所有情况，一定可以构造一种 $k = 2$ 的方法：我们设 $s^{R}$ 代表字符串 $s$ 反转之后的结果，那么回文串的结构为 $a (b) a^{R}$ ，由于 $a$ 并非全部字符相同，因此一定存在至少一个非回文前缀，那么在两端截取这一前（后）缀并交换即可得到不同的回文串。于是我们直接枚举所有 $k = 1$ 的方案，判断是否可行即可。复杂度 $O (| s |^{2})$ 。

C. Sasha and a Patient Friend

题意：有一个容量无穷大的容器可以装“耐心”，容器会以某个速率加入或抽取耐心，如果某个时刻耐心为 $0$ ，那么容器损坏。有三种操作： $1$ 、在时刻 $t$ 将容器的速率改为 $s$ 。 $2$ 、取消在时刻 $t$ 对速率的修改。 $3$ 、询问假如容器时刻 $l$ 有 $v$ 的耐心，那么在时刻 $r$ 之前容器是否会损坏，如果会那么时刻是多少，用 $d o u b l e$ 输出。

题解：考虑全局维护一棵平衡树（无旋 $Treap$ ），一个点代表一个事件，同时维护子树代表的这段时间的信息。每个点要维护这些东西：子树内事件的最早，最晚时刻，时刻最晚的事件的速率，和执行前相比，执行完子树的事件后耐心的变化量，会使容器在执行子树事件时损坏的最大初始容量。更新的过程可以通过推导求出。至于询问，只需要分裂出对应的事件，在这棵子树上二分即可。复杂度 $O (n \log n)$ 。

D. Sasha and Interesting Fact from Graph Theory

题意：求 $n$ 个点，边权为 $1 \sim m$ 的整数的所有树中，点对 $a, b$ 的距离为 $m$ 的种数是多少，模 $10^{9} + 7$ 。 $n, m \leq 10^{6}$ 。

首先有一个结论：你要给 $n$ 个点做生成树，但其中一些点之间已经有边，这些边组成了 $k$ 个连通块，某个连通块的大小为 $a_{i}$ ，那么生成树的个数为 $n^{k - 2} \prod_{i} a_{i}$ ，可以手玩矩阵树行列式来证明（或者看这里 (opens new window)）。

有了这个结论这道题就很简单了：枚举 $a, b$ 之间的边数 $i$ ，那么先有顺序的选出 $i - 1$ 个点作为中间节点，方案数为 $(\binom{n - 2}{i - 1}) * (i - 1)!$ ，在生成树中这总共 $i + 1$ 个点已经形成了一个连通块，因此在这基础上的方案数就是 $n^{n - i - 2} * (i + 1)$ ，再考虑边权， $a, b$ 之间的 $i$ 条边边权和为 $m$ ，用插板法可知方案数为 $(\binom{m - 1}{i - 1})$ ，其余边随意，方案数 $m^{n - 1 - i}$ ，因此总方案数为：

\sum_{i = 1}^{min (m, n - 1)} (\binom{n - 2}{i - 1}) * (i - 1)! * n^{n - i - 2} * (i + 1) * (\binom{m - 1}{i - 1}) * m^{n - 1 - i}

直接计算即可。

E. Sasha and a Very Easy Test

题意：维护一个长度为 $n$ 的数组 $a$ ，支持区间乘，单点除（保证可以整除），区间求和在模 $m o d$ 意义下的结果。不保证 $m o d$ 为质数。 $n \leq 10^{5}$ 。

题解：直接做比较麻烦，考虑将 $m o d$ 质因数分解，每次做在模 $p^{k}$ 意义下的结果最后CRT合并。那么每个数可以分解成 $a * p^{b}$ ，其中 $a$ 和 $p$ 互质。那么对每个数只需要记录 $a$ ， $b$ ， $a * p^{b}$ 以及对应的区间和来建立线段树，就可以完成题目的任务。复杂度 $O (n \log^{2} n)$ 。

F. Sasha and Algorithm of Silence's Sounds

题意：给定一个 $n * m$ 的矩阵，每个数在 $1 \sim n * m$ 之间并且两两不同。求有多少对 $l, r$ 满足数字 $l \sim r$ 在矩阵上的位置是一棵树（四连通）。 $n, m \leq 1000, n * m \leq 2 * 10^{5}$ 。

题解：判断是否是树有一个简单的方法：首先判断是否是森林，再判断 $点数 - 边数$ 是否为 $1$ 即可。第一步，可以发现对于每个右端点，只有一个后缀的左端点满足是森林，并且最左端的位置随最右端的右移而右移。那么这一部分可以使用 $two pointers$ 的思想，用 $LCT$ 来维护对于每一个右端点最左端的满足是森林的点。至于 $边数 - 点数$ 的限制，考虑维护一棵线段树，由于平面图的点度只有 $4$ 因此可以暴力扫描。于是就是区间加以及对满足是森林的一段区间求 $1$ 的个数。可以发现在是森林的情况下， $点数 - 边数$ 最少为 $1$ ，那么线段树只需要记录区间最小值的个数即可。复杂度 $O (n m (\log n m))$ 。