About Me

在无数久的 🐦咕咕咕 后一个新博客它建成了！

怎么都没人写好写又好懂的官方题解的做法？

考虑对询问分块。

设块大小为 $s$ ，那么每一个询问块用到过的点的数量是 $O(s)$ 的。

考虑把询问的这 $s$ 个点拿出来建虚树（这里可以 $O(n)$ 建虚树的）。我们对于一个虚树上的边，存一下这边在原树上的点的个数，白色点的个数。

然后考虑第一个操作，我们可以直接在新树上模拟进行操作。具体来说，修改一个点，如果这个点是白色直接修改，否则查一下当前操作这个点的数量是否足以递归进一个子树。递归操作即可。说白了，对关键点修改直接改，对非关键点延到块处理完了再改。复杂度是 $O(s)$。

考虑第二个操作，暴力修改子树，把每条边上白色点的个数变成原树上点的个数即可。复杂度 $O(s)$。

考虑询问，直接输出这个点的颜色即可。复杂度 $O(1)$。

考虑对一个块操作完了，我们遍历这个树，对于每个点都可以通过类似建立虚树时的办法把每个未被询问的点的颜色还原。

B 漏网之鱼

考虑求 $mex$ 这个操作，如果固定左端点，右端点不断向右移动时可以非常方便地维护这个操作。所以我们可以先固定左端点 $1$ ，向右求出每个 $[1,r]$ 的 $mex$ 值。

考虑对所有右端点维护左端点固定的时候的 $mex$ 值，现在考虑如果向右移动一次左端点，如果左端点从 $l$ 变成了 $l+1$ ，假设下一个 $a_l$ 的出现位置是 $p$ ，那么不难发现所有右端点在 $p$ 后面的区间都不会受到影响，而所有右端点在 $[l+1,r]$ 的答案会与 $a_l$ 取最小值。

如果有 $l=1,r=n$ ，我们只需要求出左端点从 $1$ 移动到 $n$ 时所有右端点用线段树维护的值的和就完事了。因为 $mex$ 函数明显单调递增，所以区间取 $\min$ 操作可以线段树。每次能取 $\min$ 的必然是一段区间，相当于是进行区间赋值操作。

但是当 $[l,r]$ 不固定，我们考虑把查询 $[l,r]$ 变成查询左右端点在 $[1,r]$ 的答案，减去左右端点在 $[1,l-1]$ 的答案，再减去左端点在 $[1,l-1]$ ，右端点在 $[l,r]$ 的答案。

考虑前两个询问怎么整，比如要查询 $[1,r]$ 的所有区间和，相当于对于左端点在 $[1,r]$ 的所有版本求出 $[1,r]$ 的区间的和。对于第二种操作，相当于是在 $[1,l-1]$ 的版本中查询 $[l,r]$ 的和。也就是说我们需要一棵求历史版本区间和的线段树。

为了方便，我们可以把区间取 $\min$ 操作变成区间加操作。具体来说，我们只有遇到值完全一样的区间才进行操作，这样就相当于是区间加法了。同时，如果这个节点最大值大于了取 $\min$ 的那个值，我们就 skip 这个区间。不难发现，每次操作我们都会合并一些段，总的合并次数是 $O(n)$ 的。

现在考虑怎么求历史版本和。我们考虑对于每个线段树节点维护一个形如 $f(t) = kt+b$ 的函数，其中 $t$ 是当前版本，$k,b$ 是我们维护的两个值。如果给这个节点上的区间集体 $+x$ ，相当于是给函数变成了 $f'(t) = kt+b+x(t-t_1)$ ，其中 $t_1$ 是当前的版本编号。于是我们可以把区间加变成了给 $k$ 加，给 $b$ 加，同时给区间打上区间赋值的标记。

这题可以点分治，但是这里写一个线段树维护凸包的做法。

首先朴素 $dp$ 的式子：

$dp[u] = \min \{dp[v] - d_vp_u\} + q_u + d_up_u$

其中 $d_i$ 表示 $i$ 的深度（带权值的），$v$ 是 $u$ 的一个祖先。

考虑由于 $s_i > 0$ ，所以 $-d_v$ 会随着深度变深单调递减，但是 $p_u$ 的变化没有规律。

这种情况往往只需要把最简单的斜率优化的凸包从直接 ++top 变成二分即可。可是这题还有着 $l_u$ 的限制，也就是我们能用的是一段根到这个点的后缀所建出来的凸包。

我们考虑使用线段树套单调栈。线段树的 $i$ 位置表示当前链深度 $i$ 的位置的点，然后线段树节点就是区间内建出的凸包（单调栈）。插入、查询就是普通的线段树修改。

首先，所有不同的操作方式是很好求的。但是不同操作序列并不正好对应一种不同的网格。

考虑什么情况下两个操作序列不同但是求出了不同的网格。如果出现了这种情况：

0 0 1 0
0 0 1 0
1 1 1 0
0 0 0 0

那么明显，要么第三行 +3 ，第三列 +2 或者 第三行 +2 第三列 +3 ，会出现两种不同的状况。

除开这种情况，不会有出现两种不同操作序列对应同一个网格图了。神仙zjk已经教了我一个绝妙的证明，可惜我懒得写下来了（逃

我们将一个导致操作序列出现不同的位置称为一个拐角，那么很明显，同一列或同一行不会出现超过一个拐角。因为在 $(i,j)$ 出现拐角，也就是这里导致了 $i$ 行，$j$ 列有两种不同的操作方式，那么 $(i+1,j)$ 和 $(i,j+1)$ 必然都是 $0$ （否则并不能对应两个不同的操作方式）。

考虑用后缀平衡树来维护这个东西。

后缀平衡树是一种维护后缀的数据结构，其中序遍历就是后缀数组。但是，对于它维护的后缀集合 $T$ 其中的一个字符串 $S\in T$ ，它可以支持 $O(\log n)$ 插入 $xS$ 。

我们考虑插入 $xS$ 的时候要做什么，首先会比较当前节点所代表的后缀的第一个字符和 $x$ 的大小关系，如果不相同，我们就已经成功比较了当前节点的后缀和这个串的大小关系。否则，我们需要比较 $S$ 与这个后缀去掉第一个字符（仍然是个后缀）的大小关系，也就是某两个后缀的大小关系。如果我们对后缀平衡树上每个点分配一个权值，可以 $O(1)$ 进行比较。分配权值可以给整个树分配一个 $[0,10^9]$ 的权值，然后每次折半分配权值。使用替罪羊树来进行重构就可以让树高保持不高。

树上后缀排序同样可以用这个，每次插入的时候可以方便地找到去掉第一个字符的后缀 $fa[u]$ 。

模拟赛的 A 题。

$dp[i][j][0/1][0/1]$ 表示当前在第 $i$ 轮，进行到了第 $j$ 场（我们把失败组的比赛和失败组胜利者与胜利组失败者的比赛压缩到一场），这一场打完了你是否是胜利者的粉丝，是否是失败者的粉丝。

然后发现这是一个类似线段树的结构，如果从 $0$ 编号，第 $i$ 轮的第 $j$ 场会由 $i-1$ 轮的 $2j,2j+1$ 转移过来。

如果是一个队的粉丝，那么显然我们会贪心地让这个队伍存活下去，不会出现一个非粉丝的队伍在失败组淘汰掉一个粉丝的队伍。因此我们不需要关心作为粉丝的队伍的数量，只需要关心是否存在。

转移，失败者里如果有粉丝队伍，那么打完后失败者一定还粉丝队伍，胜利者里有粉丝队伍，要么它维持是个粉丝的状况，要么从胜利者变成失败者。

考虑如果不强制在线，我们可以建 SAM ，于是 SAM 一个点出现次数就是前缀树子树和。

如果强制在线，也就是我们得动态维护前缀树，一个简单想法就是拿 LCT 来维护前缀树。

于是我们需要写一个 LCT ，但是显然是不需要支持 makeroot 的。

同时我们还需要求子树和。可以在 LCT 上维护子树和，具体做法就是插入一个点后直接给这个点到根的链全部 +c 。这个东西是不需要 pushup 的，删除一个点就是一个点 access 后左子树内的点全部 -c（也就是它到根的路径 -c）即可。维护这些操作只需要一个 + tag即可。

题意：对于任意 $n$ 个 $[1,D]$ 的数，求其中能找出 $m$ 对相同的数的方案数量。

首先，特判掉 $2m \le n - D$ , $2m > n$ 的情况，明显答案分别是 $D^n,0$。

稍微推下式子，不难发现题设条件即为出现次数为奇数的数个数不超过 $n-2m$ 的方案数量。

我们假设钦定 $i$ 个数字出现次数是奇数的方案数量是 $g_i$ ，恰好有 $i$ 个数被出现次数为奇数的方案数量是 $f_i$ ，那么由二项式反演我们有

$g_i = \sum_{j \le i} f_i\binom i j \Rightarrow f_i = \sum_{j \ge i} (-1)^{j-i} \binom{j}{i} g_j$

这明显是个卷积的形式，于是我们最后的答案就是

$\sum_{i=0}^{n-2m} f_i$

也就是说，只需要算出 $g$ 做个差卷积即可算出 $f$ ，从而算出答案。

4.29 模拟赛

A 参见 JOI Open 2016 摩天大楼

B 小W玩游戏

这个操作了 $q$ 次后，等价于选 $q$ 行 $q$ 列分别 $+1$ ，使得最后有不超过 $k$ 个奇数。

把行列分开讨论。考虑把 $q$ 次操作写成一个序列，每个数大小在 $1\sim n$ 。我们假设钦定 $i$ 个数字被操作了奇数次的方案数量是 $g_i$ ，恰好有 $i$ 个数被操作了奇数次的方案数量是 $f_i$ ，那么由二项式反演我们有

$g_i = \sum_{j \le i} f_i\binom i j \Rightarrow f_i = \sum_{j \ge i} (-1)^{j-i} \binom{j}{i} g_j$

所以我们只需要求出 $g_i$ 我们就可以做个差卷积变回 $f_i$ 。假设我们已经知道了 $f_i$ 的值，不难发现答案就很好求了。考虑有 $i$ 行最后被操作了奇数次， $j$ 列被操作了偶数次，于是答案就是

$\sum_{i=0}^n \sum_{j=0}^m [i(m-j)+j(n-i) \le k] f_{0,i}f_{1,j}$

其中 $f_0$ 表示通过行推出来的 $f$ ，$f_1$ 表示通过列推出来的 $f$ 。这个东西很明显可以 $O(nm)$ 求，也可以稍微化下式子，发现 $f_1$ 需要的总是一段前缀或者后缀的形式，于是可以优化到 $O(n)$ ，具体来说，就是化成：

$\begin{aligned} \sum_{i=0}^nf_0(i) \sum_{j=0}^m [j \le \frac{k-im}{n-2i}] f_1(j), n \ge 2i\\ \sum_{i=0}^nf_0(i) \sum_{j=0}^m [j \ge \frac{k-im}{n-2i}] f_1(j), n \le 2i \end{aligned}$

现在的问题就是如何求 $g$ 。

偶数的 EGF 是

$\frac{e^x-e^{-x}}{2}$

于是，我们可以写出 $g$ 的式子：

$\begin{aligned}g_i &= [x^q] q! \binom n i (\frac{e^x-e^{-x}}{2})^ie^{(n-i)x}\\&= [x^q] \frac{q!}{2^i} \binom n i (e^x-e^{-x}) e^{(n-i)x}\\&= [x^q] \frac{q!}{2^i} \binom n i \sum_{j=0}^i \binom i j e^{2xj-2ix+nx} (-1)^{i-j}\\&= \frac{q!}{2^i} \binom n i \sum_{j=0}^i \binom i j \frac{(2j-2i+n)^q}{q!} (-1)^{i-j}\\&= \frac{q!}{2^i} \binom n i \sum_{j=0}^i\binom i j \frac{(n-2j)^q}{q!} (-1)^j\end{aligned}$

明显这是个卷积的形式。

珍珠就是这题的弱化版吧？

A 钩子

我们按照 $d$ 来分层。如果当前区间长度为 $x$ ，如果它是偶数，挂一个后会变成 $\frac{x}{2}-1$ 和 $\frac{x}{2}$ ，否则会变成两个 $\frac{x-1}{2}$。就这样分层下去，最终得到的必然是 $\log$ 层。

明显每层会有一定数量的人来选，所以我们考虑对每层分别 $dp$ 。每一层明显只会有两种权值，并且我们可以知道每种权值的个数。我们考虑当前如果已经有 $i+j$ 个人选择了位置，其中有 $j$ 个人选的是奇数的块（也就是固定挂中间），$i$ 个人选了偶数的块（也就是可以选中间两个位置之一），这种情况出现的概率。通过这个 $dp$ 可以算出每个人选择奇数或者偶数的概率。注意这里选择偶数的权值应当是 $2$ ，奇数的权值是 $1$ ，因为选择偶数可以有两种选择（中间的两个位置）。

还有一点问题就是，一个偶数被选择后会出现两种情况，要么左边更短要么右边更短，这两种情况是对称的，只需要对后面的对称一下就好了。

考虑给 $T$ 建一个广义后缀自动机。我们考虑给 $T[i]$ 的所有节点全部打上 $i$ 的标记后，考虑一次询问，我们可以先倍增确定 $s[p_l\dots p_r]$ 所在的节点 $u$ ，于是就是求 $u$ 子树内出现次数最多的标记是谁。

考虑每个点开个动态开点线段树，给 $T[i]$ 所在的节点把 $i$ 这个位置加一，离线询问，然后直接 dfs 的时候线段树合并，在每个点上询问区间内最大值即可。

A 未来

注意树是按照 prufer 序随机生成的，因此树高期望为 $\sqrt n$ ，我们考虑对于每个点，计算它的所有祖先对它的贡献。

比如设当前考虑的点为 $u$ ，其祖先为 $v_1$ ，考虑设祖先到这个点的路径是 $v_1,v_2\dots v_k,u$ ，我们知道 $u$ 的贡献只和这个路径的点在排列中的相对顺序有关。那么怎么计算 $v_1$ 对 $u$ 的贡献？

我们不妨暂时将这条链重新编号，看成 $1,2,\dots k$ ，我们要统计所有排列下 $1$ 对最后的 $u$ 点的贡献。发现这个贡献其实就是所有排列的以 $1$ 开头的上升子序列个数和！考虑某种排列的某条上升子序列 $p_1,p_2,\dots p_t$，我们考虑这样一种贡献 $p_1 \to p_2 \to\dots \to p_t \to u$ ，这样就会有一种方案对 $u$ 造成了贡献。每种上升子序列对应唯一一种造成贡献的方法。

这个个数很好求，考虑枚举有多少个在 $1$ 后面的数，然后相当于我们已经钦定了这 $j + 1$ 个数字的位置，剩下的数任意排列的方案。

$\sum_{j=1}^{n-1} {n-1 \choose j} \frac{n!}{(j+1)!}$

这个可以直接暴力预处理。因为树高度期望下是 $O(\sqrt n)$ 的。

注意最终需要加上自己本身最后的贡献以及最后自己对自己的贡献（未被计算），也就是 $2\times n!\times \sum v_i$

最终复杂度 $O(n\sqrt n)$ 。

考虑 dp ，设 $dp[u]$ 表示覆盖完 $u$ 向上的边所需要的最小代价。这个怎么转移呢？

我们考虑当前 dfs 到了 $u$ 这个点，维护所有包含 $u$ 这个点的路径在钦定被选择时，覆盖完整个 $u$ 的子树所需要的最小代价。如果维护了这个，答案就是所有在 $u$ 子树内起始的路径的最小值。我们考虑用线段树维护 子树内起始的，包含这个点的最小值 这个东西。对于从这个点离开的路径，将它的这个代价设为 $\infin$ 即可。

设 $S = \sum_{v\in son[u]} dp[v]$ ，现在我们考虑怎么将一个路径从 覆盖 $v$ 的子树变成覆盖 $u$ 的子树（其中 $v$ 是 $u$ 的儿子）。明显，我们需要把覆盖 $v$ 的所有路径代价加上 $S - dp[v]$ ，相当于从其他节点选择最优情况，这个子树内钦定选择了它。

复杂度是 $O(n\log n)$ 。只需要写一个线段树区间加，区间取 $\min$ 。

考虑把每一列当成一个不超过 $2^{n}$ 之内的数，于是进行完行的修改后相当于是每个数 xor 上了一个值 $x$ ，于是我们写成式子，这种情况答案就是

$\sum_{i=1}^m \min\{popcount(a_i\ xor \ x),n-popcount(a_i\ xor\ x)\}$

我们可以设

$f(x) = \min\{popcount(x),n-popcount(x)\}$

于是枚举 xor 出来的值

$\sum_{a_i\ xor\ x = t} f(t)$

稍微移下项

$\sum_{a_i\ xor\ t = x} f(t)$

我们设 $t[x]$ 为 $a[i]=x$ 的 $i$ 的个数，那么上面东西就是

$\sum_{a\ xor\ t = x} f(t)t(a)$

这就是个 xor 卷积，然后取 min 就好了。

我们记 “恰好有 $k$ 次非平局” 的方案数是 $g(k)$ ，“钦定有 $k$ 次非平局” 的方案数是 $f(k)$ 。发现这是一个二项式反演的形式，由二项式反演有公式：（不会可以百度）

$f(n)=\sum\limits_{i=n}^m{i\choose n}g(i)\Leftrightarrow g(n)=\sum\limits_{i=n}^m(-1)^{i-n}{i\choose n}f(i)$

所以我们只要求出 $f(k)$ 就做完了这个题。我们可以 dp 求出 $f$ ，设 $dp[u][x]$ 表示 $u$ 子树内钦定选择了 $x$ 对点，这 $x$ 对点均呈 祖先 - 子孙 的关系（也就是这 $x$ 局钦定会比出胜负）。于是发现这东西可以直接树形背包算。

转移就是正常的树形背包，最后还需要考虑钦定这个点和某个后代的情况，这种情况的转移就是从子树内未被钦定的点中选择一个点。

然后我交上去的代码多输出了个 $0$ 考试的时候没看到 /kk

一个看起来挺经典的题。

$n\le 40 , m\le 10^5$

---

我们可以先考虑只有两种颜色的情况。比如只有 Red and Blue。

我们设红边权值为 $1$ ，蓝边权值为 $x$ ，那么我们可以写出一个生成函数 $F(x)$ ，并且可以设 $x^i$ 的系数是选择正好 $i$ 条蓝色边的方案数量，也就是选择正好 $i$ 条边的答案。

开始把 Ax 理解成了可以走任意A的倍数

首先，假设我们想从 $(0,0)$ 到达某个点 $(X,Y)$ ，第一种操作用了 $a$ 次，第二种用了 $b$ 次，那么有

$Axa+Bxb = X\\Aya+Byb = Y$

由 zzh 胎教时期就会的数学知识，我们知道 $a,b$ 可以被解出来。

这题其实是上次模拟赛 A 的弱化版。

（下面式子的 $=$ 都指膜 $10^9+9$ 意义下的同余）