min-max 容斥

$$\max(S) = \sum_{T \subseteq S} (-1)^{|T| - 1} \min(T)$$

证明

设容斥系数为 $f(|T|)$，则 $\max(S) = \sum_{T \subseteq S} f(|T|) \min(T)$。

考虑整体第 $k$ 小对最大值的贡献，显然当且仅当 $k=n$ 时，最小值有贡献，因此有下式：

$$[ n = k ] =\sum_{i=0}^{n-k} { n-k \choose i } f(i+1)$$

组合意义为对于大于最小值 $n-k$ 个数，可以任意选取。枚举选了 $i$ 个数，再加上固定下来的第 $k$ 小，共 $i+1$ 个数，因此乘上容斥系数 $f(i+1)$。

变换一下，可得 $[ n = 0 ] =\sum_{i=0}^{n} { n \choose i } f(i+1)$。

套用二项式反演，可知 $f(n+1)=\sum_{i=0}^n (-1)^{n-i} { n \choose i } [ i = 0 ]$。

因此 $f(n+1)=(-1)^n$，即 $f(n)=(-1)^{n-1}$。

题意

给定一棵带边权 ${ 0, 1}$ 的无根树，求回文路径的个数。

其中 $3 \le n \le 5\times 10^4$。

分析

点分治，问题转化为求有多少条过当前重心的路径，使得其构成回文串。

将从重心开始的所有结点对应的串，插入 Trie 树中，最坏情况下 Trie 树与原树同构。

分析跨越重心 $root$ 路径的回文串结构，记两个端点分别为 $u,v$，其中 $u$ 的深度大于等于 $v$ 的深度。

深度相同，则 $root$ 到 $u$ 路径对应串 (简记为 $u$ 串) 必须等于 $root$ 到 $v$ 路径对应串 (简记为 $v$ 串)。令枚举的每个结点的出现次数为 $cnt$，这部分答案贡献为 $cnt \choose 2$。

深度不同，则 $v$ 串等于 $u$ 串的后缀，且 $u$ 串的前缀是一个回文串。

因此，我们考虑对 Trie 树构建 AC 自动机，则 $u$ 串的所有在 Trie 树中有对应结点的后缀就是 fail 树上的所有祖先。注意到，fail 树上的祖先可能很多，无法枚举并检查当前前缀是否为回文串。但是，根据 $Border$ 理论，一个串的回文后缀（前缀）可以表示为 $\log n$ 段等差数列。于是，我们处理所有 Trie 树结点的等差数列 $(l,r,d)$，对应表示首项、末项和公差。这可以在构建完 Trie 树后，dfs Trie 树，并维护正串和反串的哈希值得到。

最后，枚举所有 Trie 树结点，令其深度为 $len$，再枚举其等差数列，只需要询问 fail 树的祖先上长度为等差数列 $(len-r,len-l,d)$ 的出现次数和，进一步转化可以变成求所有长度 $l \equiv ((len-l) \bmod d) ( \bmod d)$ 的点值和，考虑根号分块容易维护，但是可能会取到一些等差数列值域外的点，可以将询问离线的最大长度上，并拆成两个前缀和，在 dfs fail 树的栈上二分即可获得对应结点。

总结

1. 点分治。

2. 插入从重心开始的 Trie 树。

3. dfs Trie 树，求出每个点回文前缀的等差数列。

4. dfs fail 树，维护栈上的结点，维护栈上支持快速查询模 $b$ 余 $r$ 处点值的分块数据结构。枚举等差数列，对于公差小的，栈上二分找到询问离线点，对于公差大的，暴力枚举。

5. 枚举 Trie 树结点，计算回文前缀为空和不为空的匹配方案数。

6. 点分治容斥掉来自同一子树的配对答案数。

时间复杂度：$T(n)=2T({n \over 2})+O(n \sqrt{n}+n\log^2 n)$，$T(n)=O(n \sqrt{n})$。

E Marbles

给定一个序列，每次交换两个相邻位置，求使得数组中所有相同颜色都是连续段的最少操作次数。

颜色种数只有 $20$，注意到数组最后形态会有 $20!$ 种。

可以从左到右确定，记 $dp(mask)$ 表示左边已经确定了集合 $mask$ 的最小操作数。

转移时，枚举一个没有固定颜色，将其接在后面，因为前面的操作不会改变其他颜色的相对关系，因此操作次数等价于该颜色和其他未出现在集合的颜色的逆序对数。

题意

给定一棵树，边权带修，强制在线，询问直径。

其中 $3 \le n, q \le 10^5$。

分析

首先，给出一个引理：树上的两个点集 $A,B$，点集 $A$ 的某一条直径端点 $a_1,a_2$，点集 $B$ 的某一条直径端点 $b_1,b_2$，则两个点集之间的直径一定是这 $4$ 个点中最长的距离。反证法，容易证明。

树状数组和 LCA 解决带修路径长度。线段树维护区间的直径和直径端点。

对于修改操作，先修改边权，然后线段树上重构可能跨过这条边的线段树区间直径。

记修改边的深度大的结点为 $u$，注意到 $u$ 的 dfs 序区间内的直径一定不变，以及外部的区间一定不变，这个过程等价于在线段树上 dfs 了 $u$ 的 dfs 序区间，重构一下经过的所有结点。

时间复杂度 $O(n\log n + q \log ^2 n)$。

回到梦（题解）开始的地方？

A XORinacci

B Uniqueness

C Magic Grid

用 $[0,n^2-1]$ 填一个 $n \times n$ 的矩阵，使得每行每列异或和相同，其中 $n$ 是 $4$ 的倍数。

不知道为啥，反正观察出四个填一个 $2 \times 2$ 就行了。

D Restore Permutation

有一个排列 $p$，现在你知道对于位置 $i$，排列上前 $i-1$ 个数小于 $p_i$ 的和为 $s_i$，要求恢复出 $p_i$。

从后往前，在树状数组上二分即可。

E Let Them Slide

最大长度为 $w$，给定 $n$ 个滑动窗口，每个窗口有 $l_i$ 个数，回答 $w$ 个独立询问，所有窗口任意滑动，第 $i$ 列的最大权值和。

差分答案。

枚举每一行，枚举整个值域范围，对于位置 $i$，他可能是从窗口中某一个范围转移过来，注意到，如果窗口很短，那么中间会有很多位置只由窗口最大值贡献而来，那么我们实际上只需要枚举值域范围某个前缀和后缀，中间一部分可以在差分数组上打标记。如果窗口很长，即长度大于 $w \over 2$，那么这样的窗口最多出现 $2$ 个，因此总复杂度为 $O(\sum l_i)$。