模拟赛随机记录

记录模拟赛的好题~

10.31-T3 move

感受到了其实维护直径的功能还是很强大的。

两棵树，于是考虑在一棵树上 dfs，维护另一棵树上的信息。具体地，考虑在第二棵树上的每个点下面挂一个点，边权为 $dis1(A,u)$。考虑每次 dfs 中从 $u\to v$，其实就是一段区间的 $dis1(A,u)$ 加上边权 $w$，剩下的减去 $w$。

再来考虑距离和最大这个要求，考虑现在变成了在第二棵树上找离 $B$ 最远的点的距离，这显然可以通过维护直径做。也就是说，现在要维护的就是区间加，全局直径，直接做就行。

其实感觉是简单题啊，自己绕晕了

11.7-T3 sales

一个暴力做法显然是枚举去到的最远的位置，记选 $i$ 个数时的这个位置为 $f_i$，则显然有结论：$f_i$ 单调不降。于是考虑类似决策单调性的分治做法，每次算 $mid$ 的答案，然后分治。用主席树或精细实现的线段树维护做到 $O(n\log^2n)$。

11.8-T2 bit $\color{blue}\Diamond$

感觉是一个很新颖的角度：$\color{blue}\Diamond$ 从 popcount 的角度考虑按位与/或。有 $\operatorname{popc}(\bigvee_{x\in S}x)\ge\max_{x\in S}(\operatorname{popc}(x))$，$\bigwedge$ 同理。于是考虑枚举最后的 $\operatorname{popc}=k$，则所有 $\operatorname{popc}<k$ 的一定放在按位或中，$\operatorname{popc}>k$ 的一定在与中。

$\operatorname{popc}=k$ 的数一定只有一种。证明考虑如果多余一种，若有多于一种放同一集合显然不行，若放不同集合中，由于 $\operatorname{popc}=k$，则对应值一定等于该数，不相等。

于是只需要看这种数有多少个，讨论是全放一个集合，还是两个集合都放即可。剩下的用 st 表简单维护即可做到 $O(n\log n\log V)-O(\log V)$。

11.11-T3 spr $\color{blue}\Diamond$

怎么有人能对着第一步 dp of dp 看那么久的？

首先如果没有 $-1$ 就是简单 dp：设 $f_{i,0/1/2}$ 表示考虑前 $i$ 位，第 $i$ 位出了 $0/1/2$ 的最大分数。那么有个显然的 dp of dp：设 $dp_{i,x,y,z}$ 表示当前考虑到第 $i$ 位，$f_{i,0/1/2}$ 分别为 $x,y,z$ 时的方案数。转移显然。这是 $O(n^4)$ 的。

然后考虑优化状态。显然每一位都有一种是不能出的，所以实际上只用记录两种。设 $dp_{i,x,y,0/1/2}$ 表示 $0/1/2$ 不能出，剩下两个 dp 值依次是 $x,y$ 的方案数。$O(n^3)$。

这里看似无法优化了。$\color{blue}\Diamond$ 但是事实上对于这种记录两个数的 dp，有一个可能的优化是，由于我们并不关心两个的具体值，这题中其实最后统计答案时也只关心 $\max(x,y)$，可以考虑记录两个值的差，对于对于其他的信息可以提前处理或忽略。

对于这题，考虑令 $x=n$，记录 $y-x$，再在转移过程中处理 $x$ 和真实值之间的差带来的贡献。则设 $dp_{i,j,0/1/2}$ 表示 $y-x=j$，不能选的是 $0/1/2$ 的方案，转移时处理 $ans$ 即可。

11.13-T2 seq

首先有个显然的 $O(n^2)$ dp：设 $dp_{i,j,0/1}$ 表示当前考虑 $s$ 的前 $i$ 位，$t$ 匹配到第 $j$ 位，$s_i$ 是否和 $t_j$ 匹配是否可行。转移是 $dp_{i-1,j,1}\to dp_{i,j,0},dp_{i-1,j,0}\to dp_{i,j,0}(s_{i-1}=s_i),dp_{i-1,j-1,0/1}\to dp_{i,j,1}(s_i=t_j)$。

由于是可行性 dp，且 $n=10^5$，不难想到 bitset。转移不难表示。

但是有个问题：由于要构造，空间会爆炸。所以加上两个优化：首先构造时可以考虑，每次判断 $dp_{i-1,*,1}$ 是否可行，可行就直接去到 $1$ 否则 $0$，这样只用记录 $dp_{*,*,1}$，另一维滚动。其次发现一定有 $j\le i$，于是考虑前 $5\times 10^4$ 位用 $5\times 10^4$ 的 bitset 存，后面用 $10^5$ 的，中间衔接的时候枚举每个为 $1$ 的位置即可。于是 $O(\frac{n^2}\omega)$ 解决。

11.15-T2 show

显然要 dp，设 $dp_i$ 表示考虑 $[1,i]$ 的方案数。考虑如何转移。

首先，可以根据上一次出现的相同的数的位置确定 $>1$ 的是在奇数位还是偶数位，不妨钦定在偶数位。那么限制就分成了两部分：奇数位的数两两不同，偶数位的至少出现两次。

先考虑第一个限制，显然可以找到第一个出现相同的数的位置解决。第二个限制考虑每次加入一个 $a_i$ 时，给 $a_i$ 上一次出现的位置 $j$ 到 $i$ 打上标记，表示这些位置不能作为左端点，并且去除之前的标记。于是每次就只能从没有标记的位置转移。结合上面的，就是要求一个区间的最小值和最小值对应位置的 dp 值的和，线段树处理即可。

11.18-T4 douglas

最重要的就是如何避免算重。考虑这样一个策略：尽可能靠 $y$ 小的位置走，如果这种路线一定要往上再往上走。这样一定会不重不漏地算上每种走法。

再考虑如何计数，不难发现这样一定是一直往右走，直到某个位置往上再往右一步走到 $(x_1,y_2+1)$。于是扫描线，维护区间求和，区间推平，单点赋值。同时对于障碍堵住的位置，再开个线段树/set 维护一下哪些位置不能经过再处理即可。

11.19-T4 d

首先将问题转化为：将 $[2,2^n]$ 内的数分成 $n$ 个大小分别为 $2^0,2^1,2^2,\cdots,2^{n-1}$ 的集合，使得每个集合中的最小数都不在 $S$ 中。但是发现都不在 $S$ 中这个条件比较难看，考虑容斥变成钦定若干个集合的最小值在 $S$ 中，其他任意。为什么这样会比较好做？因为限制了 $|S|\le 100$ 使得我们可以考虑从这里入手。

于是进行一个 dp。考虑从小到大判断每个 $S$ 中的数是否为某个集合的最小值，如果是就选一个集合放，否则任意填进已经选了的集合里面的一个空位。对于不在 $S$ 内的数则也是找空位填。但是每个集合大小不同，不过只有 $n$ 个集合，于是考虑直接状压。设 $dp_{S,i}$ 表示当前已经钦定了最小值的集合为 $S$，选到第 $i$ 个在 $S$ 集合中的数的方案数。转移乘上组合数即可。$O(2^n|S|n)$ 解决。

11.21-T4 graph $\color{blue}\Diamond$

一种很新的线段树分治。

首先考虑判定。不难发现有解当且仅当每个连通块大小都为偶数，证明是简单的。同时显然答案单调不升。于是考虑从后往前做，每次不断加权值最小的边直到满足条件。

但是发现一个问题：加边之后，由于每条边存在的时间是一个后缀，所以还要删边。怎么办？$\color{blue}\Diamond$ 考虑线段树分治，但是当处理 $t$ 的时刻的答案时，考虑找到这条边的出现时间 $l$，于是这条边事实上会对 $[l,t]$ 内的询问有贡献，再拆成 $[l,t-1]$ 和 $[t,t]$，于是在加入这条边时再在 $[l,t-1]$ upd 这条边即可。

11.22-T4 calc $\color{blue}\Diamond$

$\color{blue}\Diamond$ 对于这种计算每个点对之间的贡献的题，可以考虑分治。

首先对于 $r-l$ 比较小的（$\le 10$）的可以直接暴力。然后考虑当前分治中心为 $mid$，计算 $i\in[l,mid],j\in[mid+1,r]$ 的 $d(i,j)$ 的贡献。

容易发现，$(i,j)$ 之间路径一定经过 $mid+1,mid+2,mid+3$ 之中至少一个点，因为一次最多跳 $3$ 的距离。于是处理出 $f_{i,j}=d(i,mid+j)$，则要求的就变成了 $\sum_{l\le i\le mid}\sum_{mid+1\le j\le r}\min_{k\le 3}f_{i,k}+f_{j,k}$。

$\color{blue}\Diamond$ 对于这种计数若干个 $\min$ 的和的问题，考虑钦定一个为 $\min$，然后计算它真正为 $\min$ 时的贡献。不妨钦定 $f_{i,1}+f_{j,1}$ 为 $\min$，则条件为 $\begin{cases}f_{i,1}+f_{j,1}\le f_{i,2}+f_{j,2}\\f_{i,1}+f_{j,1}\le f_{i,3}+f_{j,3}\end{cases}$。移项，把和 $i$ 有关的以及和 $j$ 有关的分开，$\begin{cases}f_{i,1}-f_{i,2}\le f_{j,2}-f_{j,1}\\f_{i,1}-f_{i,3}\le f_{j,3}-f_{j,1}\end{cases}$。不难发现这是一个二维偏序的形式，离线下来排序，然后扫描线，用 BIT 维护解决。时间复杂度 $O(n\log^2n)$。

11.23(PNR round 8)-T3

首先考虑给定柱子高度如何算总积水。考虑柱子 $i$ 的积水高度，设 $f_i=\max_{j\le i}h_j,g_i=\max_{j\ge i}h_j$，则高度为 $\min(f_i,g_i)-h_i$，即总积水为 $\sum\min(f_i,g_i)-h_i$。

因为 $\min(f_i,g_i)$ 既和前面的有关又和后面的有关，于是考虑如何去掉这个 $\min$。不难发现 $\min(f_i,g_i)$ 取 $f_i$ 的 $i$ 是一段前缀，取 $g_i$ 的是剩下的后缀。若令 $f_i\le g_i$ 时取 $f_i$，则这个分界点，即最后一个取 $f_i$ 的位置是最后一个全局最大值的位置。

于是枚举操作完后最后一个全局最大值的位置 $p$，则可以分开算 $\sum_{i\le p}f_i-h_i$ 和 $\sum_{i>p}g_i-h_i$。对于前面的，考虑设 $dp_{i,j,k}$ 表示当前枚举到 $i$，已经选了 $j$ 个变为 $0$，当前的最大值位置在 $k$ 的方案数。转移枚举这一位选不选，再看最大值是否变化即可。后者也是类似的。统计答案的时候枚举左右两边各选了多少个，以及右边的最大值即可。时间复杂度 $O(n^2k)$。

考虑优化，不难发现由于最多删 $k$ 个数，所以不同的前/后缀最大值最多只有 $k+1$ 个。预处理出这 $k+1$ 个前/后缀最大值，合并答案时也是一样，不同的全局最大值只有 $O(k)$ 个。依据实现做到 $O(nk^2)$ 或 $O(nk^3)$。

后面都是省选模拟赛。

12.3-T1 count $\color{blue}\Diamond$

下令 $n\leftarrow nk,B\leftarrow n$。

首先有个暴力做法：每次直接枚举 $i,j$ 算。复杂度为 $O(nB)$。

$\color{blue}\Diamond$ 由于数据范围限制了 $n$ 的大小，所以考虑找出另一种做法，类根号分治。

$\color{blue}\Diamond$ 同时对于这种算某个东西的 $k$ 次方，可以考虑拆开算每一项的贡献（ARC124E）。对于这题，拆成 $(\sum a_j2^j)^3$ 的贡献。考虑枚举三位 $i,j,k$，产生贡献当且仅当这三位异或起来都是 $1$，处理出 $c_x$ 表示 $i,j,k$ 三位的值拼在一起为 $x$ 的 $a$ 的个数，则贡献的对数为 $\sum_{i<4}c_i\times c_{i\oplus 7}$。这样复杂度为 $O(\frac{n^3}{B^2})$。

结合在一起，容易发现当阈值取 $B=n^{\frac23}$ 时复杂度取得最小值 $O(n^{\frac53})$。但是还是无法通过。

$\color{blue}\Diamond$ 但是由于是一堆异或运算，容易想到 bitset 优化。对于做法 $1$，考虑类似 bitset 地 $\omega$ 位一块，每块算异或和，复杂度 $O(\frac{nB}\omega)$。对于做法 $2$，考虑预处理出 $a_{i,j}=0/1$ 的 $i$ 的 bitset，于是可以 $O(\frac n\omega)$ 得到一个 $c_i$ 的值。复杂度变为 $O(\frac{n^32^k}{B^2\omega})$。取 $B=n^{\frac23}2^{\frac k3}$，复杂度为 $O(\frac{n^{\frac 53}2^{\frac k3}}{\omega})$ 可以通过。

12.4-T1 graph $\color{blue}\Diamond$

对了 3h 脑电波。

首先找出一棵生成树并进行编号。如果一直从“确定某个点的编号”的方向考虑是非常没有前途的。仔细思考，如果每次到一个编号未知的点再返回就不用确定编号了。问题就变成了能从这里获取什么信息。

$\color{blue}\Diamond$ 灵光一闪想到拆位。具体地，进行 $\log_3n$ 轮，每轮将 $u$ 点染成 $(n)_3$ 的一位，对于每条非树边，在祖先的位置询问后代的编号的三进制这一位的值，则最后就能拼成真实值。精细实现刚好 $14m$。1

12.4-T2 kte

由于上述原因，赛时会了没打出来。

首先设 $f_i$ 为当前前 $i$ 小的和，$g_i$ 为前 $i$ 大的和。则答案显然为所有 $[f_i,g_i]$ 的并集。但是这个完全不能维护。此时发现比较烦的是有区间之间有交的情况，于是想怎么处理这种情况。

这里就有一个非常厉害的性质：注意到在 $i\le\frac n2$ 时，若 $g_i\ge f_{i-1}$，则对于 $g_{i+1}=g_i+x,f_i=f_{i-1}+y$，由于 $x>y$，所以一定有 $g_{i+1}\ge f_i$！对于 $i>\frac n2$ 的情况也是类似的。于是可以二分出这两个边界，中间的就是 $\max g_i-\min f_i$，剩下的就是 $\sum g_i-f_i+1$。线段树维护即可。

12.5-T1 game

考虑嗯推 SG。太有趣了！

首先不妨考虑一条链的情况。设 $d_u=\max_{v\in\operatorname{subtree}(u)} dep_v$，则不难发现整条链可以视为一个二进制数，$sg_u=\sum_{c\in\operatorname{subtree}(u),c_v=1}2^{d_u-dep_u}$。

考虑拓展成树。首先如果操作了根，则剩下的是个若干个子问题，则 $sg_u=\bigoplus_{v\in son_u}sg_v$。又由于操作完后 $\max sg_v=2^{d_u-dep_u}-1$，则 $sg_u\ge 2_{d_u-dep_u}$。

还能不能更大？剩下的情况一定是不操作根节点的，于是一定有 $sg\ge sg_u$。此时直接忽略根节点，则 $sg=\bigoplus sg_v$。然而所有后继状态都能到达 $sg<2^{d_u-dep_u}$ 的 $sg$ 值，于是就有 $sg_u=\bigoplus sg_v\oplus 2^{d_u-dep_u}$。dp 上去就行了。

好麻烦。

12.5-T2 seq $\color{blue}\Diamond$

首先不管 $P,|N|$，用一个二元组 $(x_i,y_i)$ 分别表示当前 $a_i\ge 0$ 和 $a_i<0$ 的 $a_i$ 之和。则不难发现最后要求的形如 $\max ax+by$。不难发现这需要维护一个下凸包。

于是现在需要维护的就是：区间 $x_i,y_i$ 加 $k$，在凸包上二分。$\color{blue}\Diamond$ 注意到对一个点集里的所有点的 $x_i,y_i$ 整体加不会影响凸包，于是考虑序列分块/操作分块。当时写了操作分块，具体就是每 $\sqrt m$ 个操作一块，则能保证 $\sqrt m$ 块内，每块的凸包形状都不变。于是询问就在这些凸包上面二分即可。

序列分块似乎更好写，总之复杂度都是 $O(m\sqrt{m\log m})$。

12.6-T1 i $\color{blue}\Diamond$

从点分树的角度考虑。考虑如果已经知道了两棵树分别的点分树形态，如何合并这两棵点分树。

这里场上犯了一个错误，就是过于在意原本的树对应合并后的树的实际形态，于是方向一直是把原来的树就拆成若干个连通块记录。$\color{blue}\Diamond$ 事实上可以直接把原来的树记录，再考虑树的合并。

考虑 $u$ 子树的点分树的根 $rt_u$ 以及 $v$ 的 $rt_v$。如果在不影响原本两棵点分树的相对形态的基础上合并的话，那么首先新树的根一定是 $rt_u$ 或 $rt_v$，不妨令其为 $rt_u$。然后此时除了 $u$ 所在子树都已经是确定了，于是考虑 $u$ 子树方向的下一个点，则一定是原树这个方向的下一个点或 $rt_v$。以此类推，发现本质上只需要将 $rt_u\to u,rt_v\to v$ 的两条链合并。于是设 $dp_{u,i}$ 表示 $u$ 子树形成的点分树中，$dep_u=i$ 的方案数，每次网上合并即可。

12.6-T2 ii $\color{blue}\Diamond$

套路扫描线，然后发现要维护的就是两种操作：区间和 $k$ 取 $\min$，区间查询 $\ge l$ 的个数。由于 $\ge l$ 的一定在查询区间中，所以实际上是全局查。

考虑第一种操作，肯定需要 Segment Tree Beats 维护。于是考虑怎么维护后者个数。$\color{blue}\Diamond$ 考虑一个很本质的东西：Beats 实际上就是将一次区间取 $\min$ 操作变成 $O(\log n)$ 次区间将某个数全部变成另一个数的操作。于是再开一个 BIT 维护每种数有多少个，每次就是单点加减，最后直接查询即可。

12.8-T1 venture

std 做法好像非常简单，就是类似处理哈希冲突那样找到第一个没有填的点填上……

考虑如果一共要进行 $x$ 次攻击，则意味着 $[1,x]$ 内的每一次攻击都要触发。于是答案就是 $\max_{i\le x}i-\sum\left\lfloor\frac{i-1}{a_j}\right\rfloor$。于是有一个 $O(n\log n\ln n)$ 做法就是每次加入的时候，如果会产生影响就枚举 $O(\frac na)$ 修改。上界是每个 $a$ 被枚举两次。

然后考虑单 $\log$。考虑记 $f_i=i-\sum\left\lfloor\frac{i-1}{a_j}\right\rfloor$，则 $f_i$ 的前缀 $\max$ 一定是 $[1,*]$ 连续的一段。考虑直接维护前缀最大值的位置，则每次就形如找若干个位置删掉，查询某个前缀的没有删掉的数量。由于只会删 $O(n)$ 次，于是精细实现就是 $O(n\log n)$ 的了。

12.9-T1 tree

容斥！容斥！

首先又是那个 trick：看到 $x^k$，拆成若干项的贡献。那么问题就变成了若干个颜色一定出现的方案数。注意到我们并不关心具体是哪些颜色，于是算一次，最后乘上组合数。

然后考虑若干个颜色一定出现，典型的容斥，变成钦定若干个颜色不出现的方案数。然后考虑数这个东西。如果没有限制的话，考虑先定一个点，剩下就全是 $m-1$。但是发现这个做法可拓展性不强。

此时注意到我们要求“所有相邻的点的颜色都不相同”，这也是一个容斥的性质。考虑钦定若干条边对应点一定相同，于是分成若干个连通块分别算。而这样每个连通块的方案数就只和其中是否包含关键点有关，非常简洁。于是设 $dp_{u,0/1}$ 表示当前 $u$ 所在连通块是否有关键点，合并子树时考虑相连的边选不选，同时转移方案数和容斥系数。最后再根据这个求答案即可。

12.9-T2 cut

考虑如果只能选一条树边，那么令分开的子树为 $u$，则 $u$ 子树内的非树边一定全都要删去。那么如果还有另一个分开的子树 $v$，容易发现此时 $u$ 子树连向 $v$ 子树的边就不用删了。于是设 $f_i$ 表示 $i$ 子树内非树边的数量，$g_{i,j}$ 表示 $i$ 子树连向 $j$ 子树的数量。则 $ans_i=\min_jf_i+f_j-2g_{i,j}$。

由于数据范围小且 3s 时限，于是直接静态链分治，对于每一棵子树分别算，那要维护的就是链加全局最小值。$O((n+m)\log^3n)$ 冲即可。

12.11-T1 kristoff

很 ARC 风格的题，不过放 ARC 最多 2700？

首先考虑找出所有极长的可操作区间。容易发现这些区间一定是不交的。然后还有个性质：每次操作一定会操作一个极长的可操作区间，否则一定不优。证明是简单的。

然后就只用考虑每个极长区间的第一个和最后一个字符 $a_i,b_i$。更进一步，由于 $b_i=a_{i+1}$，于是只用考虑 $a_i$。再考虑现在每个操作的影响，容易发现，一次操作就是选择 $a_i\not=a_{i+1}$ 然后删掉 $a_i,a_{i+1}$。这是经典问题，只需要每次找剩下数量最多的字符删即可。

12.11-T3 zdd

转换题意，每次修改相当于给这条边一个 $t$ 的标记，询问就是问从 $u$ 开始，走单调上升的标记能到达的点的数量。显然能到达的点形如一个连通块。

既然是连通块，想到点分治。对于一个分治重心 $rt$，考虑求出每个点 $u$ 最早到 $rt$ 的时间 $f_u$ 以及每个标记 $i$ 最晚什么时刻从根出发能到这个标记 $g_i$。则若询问 $(u,t)$ 能到达 $v$，则存在一个在 $v$ 的父边上的标记 $i$，满足 $f_u<g_i,i>t$。扫描线维护即可。

12.13-T3 greatcar

观察题面，发现限制形如若干个区间，每个区间内的车数量大于/小于等于某个数。考虑转成前缀和 $f$，并且把车变成一个点。同时注意到实际上有用的位置不是很多，离散化，于是限制就变成了：

• $f_i\le f_{i+1}$

• $f_i\le f_j+\left\lceil\frac{i-j}{k}\right\rceil$

• $f_i\ge f_j+\sum[a_p\ge j\wedge b_p-k\le i],(j<i)$

• $f_{y_i-k}\le f_{x_i}+c_i$

于是显然可以差分约束。但是如果直接跑 spfa 是 $O(n^3)$ 的。于是考虑用脑求负环。

不难发现负权边只有 $f_i\ge f_j+\sum[a_p\ge j\wedge b_p-k\le i],(j<i)$。同时，容易发现如果有负环，则一定存在一个负环只有一条负权边。证明考虑 $i\to j$ 的边权是被 $[i,j]$ 完全包含的 $[a_i,b_i-k]$ 区间的个数。于是如果走了 $i\to j,j\to k$ 显然不如直接走 $i\to k$。（不过实际上就算没有这个性质也能做？）

于是现在只需要求出 $dis_{i,j}$ 表示只走非负权边，$i\to j$ 的最短距离。直接暴力跑还是 $O(n^3)$ 的。但是可以发现，这里的瓶颈在于 $f_i\le f_j+\left\lceil\frac{i-j}{k}\right\rceil$ 的边有 $O(n^2)$ 条。但是容易发现这是一个很好维护的形式，只需要拆开下取整，变成和 $i\bmod k$ 有关的问题就能用 SGT 维护转移。时间复杂度 $O(n^2\log n)$。

1.19 T2-B

首先最少删的数量显然为 $\left\lfloor\frac n2\right\rfloor\times\left\lfloor\frac m2\right\rfloor$。

考虑 $n,m$ 皆为奇数的情况。容易发现每个 $x,y$ 皆为偶数的 $(x,y)$ 都一定要删。答案为 $1$。

再考虑有一个奇数的。不妨令其为 $n$。于是发现 $n$ 这边的横（？）坐标就已经是确定的。而 $m$ 这边，每一行都有可能有一段前缀，删除的位置 $y$ 为偶数，剩下的后缀为奇数。于是方案数即为 $(\frac m2+1)^{\frac{n-1}2}$。

剩下 $n,m$ 皆为奇数的情况是否是把另一维的贡献也乘上就行？手玩样例可以发现有一种情况不合法：

.#..
...#
#...
..#.

这种情况中每一行/列对应的都是合法的，但是中间空出来了一个 $2\times 2$ 的块。同理，对这个情况水平对称一下也不合法。

于是考虑 dp。注意到 $n\le 25$，也就是 $\frac n2\le 12$。于是考虑状压记录一个状态。设 $dp_{i,S,j}$ 表示当前考虑到第 $2i-1,2i$ 列删除的位置，其中每一个删除位置的列坐标的奇偶性为 $S$，并且前 $j$ 个的行坐标为偶数的方案数。从 $dp_{i-1,S,j}$ 转移到 $dp_{i,*,k}$ 时，$S$ 中有些为 $0$ 的位置一定要变成 $1$。其他 $0$ 任意。于是把强制变成 $1$ 的位置统计上，然后高维前缀和即可。

时间复杂度 $O(m2^{\frac n2}n^2)$，但是由于带很多 $\frac 12$ 的常数所以可过。

1.19 T3-C

考虑二分答案。建出 kruskal 重构树。$u,v$ 都尽可能往上跳，即找到能到达的最大连通块。然后只用判断是否有连接这两棵子树的边。直接线段树合并预处理出每个子树能到的点的 $dfn$，查询的时候只用在线段树上查询一段区间的和是否 $>0$ 即可。$O(q\log m\log V)$。

2.6 T3-conquer

比较套路的 dp of dp 题，但是赛时心态爆炸所以没开。

首先计数指定 lcs 的序列，听起来就很像 dp of dp。求 lcs 的 dp 是简单的，即 $f_{i,j}=\max(f_{i-1,j},f_{i,j-1},f_{i-1,j-1}+[s_i=t_j])$。考虑状态怎么设。考虑当前处理到 $T$ 的第 $i$ 位，首先要存下一些原 dp 的状态，但是把所有 $dp_{j,i}$ 都存下来是不可能的。

此时发现由于要求 $lcs>n-k$，所以如果 $T$ 的第 $i$ 位匹配到了 $j<i-k$ 或 $j>i+k$ 显然都是不可能的了。此时状态数为 $O(n^{2k+2})$。

同时还能发现，显然有 $0\le f_{j,i}-f_{j-1,i}\le 1$，所以只需要记录 $f_{i-k,i}$ 的值，剩下每一位状压，就是 $O(n^22^k)$ 的。

再再再观察，发现一定有 $f_{i-k,i}\in[i-2k,i-k]$，否则 $f_{i,i}<i-k$，显然无法找到长为 $n-k$ 的 lcs。于是状态数只有 $O(nk2^{2k})$ 了。可以接受。

再考虑转移。如果暴力枚举当前位置字符就是 $O(n|\Sigma|k^22^{2k})$ 的，不太行。但是再再再再发现，对于一个位置 $i$，如果和某个位置 $j$ 匹配在最后的 lcs 中，那么 $|i-j|\le k$，于是这个位置能填的本质不同的字符只有 $O(k)$ 种。$O(nk^32^{2k})$ 可以通过，但是题解说可以 $O(nk^22^{2k})$ 不是很懂，看了 std 似乎是他写错了。。。

2.6 T2-cover $\color{blue}\Diamond$

不管怎么样，我觉得需要利用到模数性质写一句“由于答案可能很大……”是非常不负责任的表现。。。总之尽量讲讲吧？

由于模数为 $2$，于是很可能就是构造双射去掉很多情况然后做，并且可以用 $最小点覆盖=n-最大独立集$ 转化。场上到这里就不会了。

$\color{blue}\Diamond$ 事实上一个可能的思路是关注一个极小部分，并通过构建双射去掉一部分状态。考虑直接拎出来两个点，比如 $1,2$。考虑除了 $(1,2)$ 之外边，此时 $1,2$ 的邻域如果不同，那么此时交换 $1,2$ 的邻域显然图是同构的，于是最大独立集相同，直接抵消掉。否则？不难发现 $1,2$ 完全相同，不妨直接合并成一个点往下做。

以此类推，我们每次可以对两个在原图中对应的点数相同的点进行如上操作。最后一定会形成若干个对应原图 $2^{k_i}$ 个点的大点。此时再算最大独立集，就可以贪心地枚举 $k_i$ 最大的点，能选直接选。并且这个状态显然可以压进一个 $\le n$ 的二进制数 $K$。

但是我们还没算方案数！不过此时可以通过贪心的方式选点，于是。很难注意到另一个非常厉害的性质：如果存在一个没有选的点 $i$ 和一个 $k_j<k_i$ 的 $j$，那么 $i,j$ 间是否有连边不影响。证明考虑，判断 $i$ 是否取的时候不关心 $j$ 的状态，判断 $j$ 是否取时，由于 $i$ 一定不取，所以这条边存在与否也是没有影响的。于是此时又形成了双射。

所以我们只需要关注全部点都取或者只有 $k_i$ 最小的点没有取的情况。固定序列 $k_m$ 时，考虑算分别的方案数。前者显然为 $1$，后者考虑只有 $k_i$ 最小的点和其它点的可能连边，但是不能全不连，于是为 $2^{m-1}-1$，都为奇数。对应地，图的最大独立集就分别是 $K,K-\operatorname{lowbit}(K)$。

那问题只剩下如何求出状态为 $K$ 的点集的方案数。设 $dp_{i,S}$ 表示原图有 $i$ 个点，上述状态为 $S$ 的方案数。考虑加入一个点，要不就是加进去不断合并，$dp_{i-1,S-1}\to dp_{i,S}$。要么就是合并到一半被删掉了，那么此前 $S$ 后面的 $0$ 全都是 $1$。$dp_{i-1,S+\operatorname{lowbit}(S)-1}\to dp_{i,S}$。然后再处理答案。$O(n^2)$ 预处理即可。

2.8-T3 luck

一句话：每次询问枚举短的路线，在长的上二分，再记忆化可过。

考虑分析复杂度。记 $k=\sum K_i$。询问 $x,y$，令 $K_x<K_y$。若 $K_x\le\sqrt k$，显然每次不会枚举超过 $O(\sqrt k)$ 个位置。这部分是 $O(q\sqrt k\log k)$ 的。

否则，考虑每个位置被枚举了几次。因为 $K_y>\sqrt k$ 所以不同的 $y$ 最多有 $\sqrt k$ 个。记忆化之后，每个位置就会被枚举到不超过 $\sqrt k$ 次。所以这部分是 $O(k\sqrt k\log k)$ 的。

2.9-T2 game $\color{blue}\Diamond$

首先考虑 $S=2$ 怎么做。发现每一行只有两个数，这就让人很想连边。连完边就想在这个图上走路。那首先容易发现，如果可以走出一条回路，每条边按照走的方向确定这行的元素顺序，那么对于回路中出现的所有元素，这部分在两列中出现的次数都是一样的。那么如果原图有一条欧拉回路那就显然结束了。

但是很多时候没有。但是发现对于奇度数的点，在某一列多放一个没有什么影响。而如果走出一条路径，只有两端的元素在两列中的数量不是一样的。于是只需要每次消掉两个奇度数点，剩下的再对每个连通块跑欧拉回路即可。实现上，直接枚举每个奇度数点，随便 dfs 一条路径直到走不了就能消掉两个奇度数点。剩下随便 dfs 就行。

和 yhd 交流的时候知道了上面那个东西也可以用之前忘了哪次讲题的，$\color{blue}\Diamond$ 建一个虚点连所有奇度数点的 trick 做。没想到。

然后考虑 $S>2$。发现我们这个构造方法是非常强的，一定有解。然后发现一个性质：将 $x$ 尽可能平均分成 $2^k$ 份，可以通过重复 $k$ 次：对当前每一份都尽可能平均分成 $2$ 份 的过程完成。于是每次把前一半的视作 $S=2$ 时第一列的，剩下的视作第二列的，做 $S=2$，再递归求解即可。

2.9-T1 swap $\color{blue}\Diamond$

题解第一步讲的非常好！直接放了。

考虑我们是要求 $f(S,l,r),T$ 相同的位置数，其中 $f(S,l,r)$ 表示 $S$ 经过 $[l,r]$ 内的操作后的结果。这个东西不好求，$\color{blue}\Diamond$ 发现一个原因是 $l,r$ 两个未知数都在左边，于是考虑移到右边来。考虑两边同时进行 $[r+1,n]$ 的操作，显然要求的答案不变，但是这样就变成了 $f(S,l,n),f(T,r+1,n)$ 相同的位置数。显然都是可以预处理的。

然后考虑求答案。顺便参杂一点赛时的想法：$\color{blue}\Diamond$ 注意到，如果我们枚举一个端点再考虑这个端点的最大答案，我们并不知道答案这些位置是哪些，所以大概率还要枚举，不能接受。于是直接考虑枚举答案位置。

然后还有一个关键的结论，$\color{blue}\Diamond$ 就是 $\operatorname{popc}(S\oplus T)=k-\operatorname{popc}(S)-\operatorname{popc}(T)+2\operatorname{popc}(S\&T)$。证明不难。于是 $popc(S\&T)$ 越大越好，枚举时也可以考虑直接枚举 $S\&T$ 算。

所以剩下的只需要对于一个 $K$，求出最小的 $l$，最大的 $r$ 使得 $K\subseteq f(T,r+1,n),K\subseteq f(S,l,n)$。处理出 $f(S/T,*,n)$ 后高维前缀最值即可。

2.10-T1 stone

首先题意即为在一个区间集合中选出若干个区间，最小化其交集，其次最小化区间的 $\max r-\min l$。不难发现最优情况下一定只用选两个区间，并且第一问的答案为所有区间的交集。

若交集非空，则选出以交集左端点为 $l$ 的区间中的 $\min r$，右端点同理。否则，考虑对于每个位置，维护以其为 $l$ 的 $f_i=\min r$ 以及相对应的，$g_i\max l$。于是要求的即为 $\min_{i<j}f_i-g_j$。不难发现这可以在线段树 pushup 时合并地维护。

2.13-T2 education

快进到 link（

给出题人好评，部分分相当有提示意义。

首先考虑 $B\le 18$。由于每个点只和与其绝对值 $\le 18$ 的点有关，于是从小到大枚举点，状压前 $18$ 个点的状态即可 $O(n2^B)$。

然后考虑 $B\bmod A=0$。考虑对于 $|u-v|=A$ 的一条链，上面 $|u-v|=B$ 的边会分成若干条小链。对于 $B>20$ 的情况，这些小链长都 $\le 10$，依次枚举每条小链，状压其状态，再处理大链上的边是否选即可。

再考虑 $B>100$ 的情况。不妨变成 $2B>n$ 的情况。手玩一下小的图就会发现，可以通过某些排列这些点的方式，使得整张图变成一个类似网格图，但是有一条边从第一行连向最后一行的形状。再拓展一下，手玩一下 $n=22,A=4,B=7$ 的情况，发现此时变成了有三条这样的边。

然后思考一下是为什么，发现考虑这样一张图：每个点 $u$ 的右边是 $u+B$，下面是 $u+A$，则这张图呈循环阶梯状二维彭罗斯阶梯。同时注意到每一行至多有 $\left\lfloor\frac nB\right\rfloor$ 个点，则对应的竖着的边这是大概这个数量。然后结合上面的，只要断掉某一行的所有边，就变成了一个一般的阶梯状网格图。

然后考虑一个 dp：设 $dp_{i,S}$ 表示当前处理到第 $i$ 行，该行从左到右每个点是否被选的状态为 $S$ 的方案数。考虑转移。行间转移考虑为 $1$ 的对应位置一定为 $0$，否则存在对应的行间的边则对应位置可 $0$ 可 $1$。于是可以高维前缀和。行内的转移考虑类似高位前缀和或称 FMT 或称轮廓线 dp，依次枚举每条行内的边，枚举对应两个位置皆为 $1$ 的状态转移到皆为 $0$ 的状态。

这样做的复杂度，由于还要枚举断开的边的状态，所以是 $O(n2^\frac{2n}B)$ 的。根号分治，$B\le 20$ 时跑上面的 $O(n2^B)$，否则跑这个。可以通过。

其实看到部分分就猜到是根分了，而且之前似乎做过类似的题，翻转硬币。

2.14-T2 send $\color{blue}\Diamond$

赛时都差不多想到了，就是思维太固化了！

显然可以先跑一次最大费用任意流（$dis_T<0$ 时直接 return），不在这个流中的边答案就是这个最大费用。

否则考虑强制退掉一条边的流会发生什么。容易证明流量的变化量不会超过 $1$。但是做到这里赛时的思路是：如果流量 $+1$，那么就相当于要选出一条 $S\to v$ 和一条 $u\to T$ 的最长路，并且要求两条路径在边上不交。但是不交这个条件非常难处理。

但是注意到 $n,m\le 2000$，所以让 $S,T$ 为不变量反而影响了问题的解决，$\color{blue}\Diamond$ 不如每次固定 $u,v$ 作为起点，这样可以在 $S,T$ 之间连一条虚边，然后所有的情况就都能转化成 $u\to v$ 的一条路径了。后面的不是很重要。

2.17-T1 square

考虑只有两种本质不同的情况：$x_i<x_j<x_k\wedge y_i<y_j<y_k$ 或 $x_i<x_j<x_k\wedge y_i>y_k>y_j$。其他情况只需要对称一下。第一种是简单的，考虑第二种怎么算。

钦定 $c_i=0,c_j=1,c_k=2$。对 $y$ 坐标离散化，从左往右扫描线。考虑计算一个 $j$ 的答案。对于每个 $y$，维护 $y_k=y$ 的 $k$ 中的 $g_y=\min x_k$，以及 $y_i>y_k$ 中的 $f_y=\min y_i-x_i$，以及 $h_y=f_y+g_y$。（注意这里的 $i,j,k$ 要同上，即要求 $x_i<x_j<x_k$，下文也用 $i,j,k$ 表示位置关系）。

考虑做扫描线的时候会有什么影响。首先可能有一个 $c_k=0$ 的 $k$ 变成了 $i$，那么 $\forall y\le y_k,f_y=\min(f_y,y_k-x_k)$。然后可能有一个 $c_i=2$ 的 $i$ 变成了 $k$，那么 $g_{y_i}=nxt_i$，其中 $nxt_i=\min\limits_{x_p>x_i\wedge y_p=y_i}x_p$ 。

于是需要维护的就是区间 $f_y$ 取 $\min$，单点 $g_y$ 修改，并且到前者可以变成二分后区间赋值。可以直接线段树维护，因为区间赋值时 $f_y$ 全部相同，那么线段树端点上就一定有 $h_u=f_u+g_u$，直接维护就行。

2.17-T2 xor $\color{blue}\Diamond$

首先容易发现最后 $a_i$ 的值为 $a_i\oplus\bigoplus_{j\in S}a_j(S\subseteq[1,i-1])$。构造考虑每个 $S$ 中的元素表示成 $[j,i-1]$ 去掉 $[j+1,i-1]$，而 $a_i\leftarrow a_i\oplus [*,i-1]$ 是简单的，并且操作完后倒序进行前面的操作就可以还原。从大到小构造所有 $a_i$ 即可。

那么此时就有了一个 $O(n^2\log V)$ 的做法。设 $dp_{i,j}$ 表示前 $i$ 个，选了长为 $j$ 的子序列，子序列最后一个数的最小值为 $dp_{i,j}$。转移只用求出来在 $\{a_k|k<i\}$ 中选若干个数异或起来再 $\oplus a_i$ ，使得这个值 $>dp_{i,j}$ 且尽可能小。$\color{blue}\Diamond$ 求这个值只需要让 $a_i$ 与线性基无交（类似 rebuild）然后再按位贪心。

考虑优化。不难发现线性基只会变化 $O(\log V)$ 次。如果将 $a_i$ 插入线性基后，线性基没有变化，则这个 $a_i$ 最后的取值为在 $\{a_k|k\le i\}$ 选若干个异或起来。再考虑如果连续的一段都是这样的，或者只有开头有限制，那么若其中选的第一数在线性基能组成的数中排名为 $x$，则后面的数依次是 $x+1,x+2,\cdots$，于是可以单调队列维护这一部分的转移。

这是 $O(n\log^2V)$ 的。单 $\log$ 的如果我没退役就有极小概率补。

2.19-T2 seq $\color{blue}\Diamond$

注意到一个重要的限制是 $\bigoplus p_i=d$，这个限制没有什么很好的处理方法，$\color{blue}\Diamond$ 不过可以考虑某些情况下，有一个 $p_i$ 可以任意取，那么只用确定其他的 $p_i$，最后再用这个满足限制。

然后还要考虑一下如果已知 $p_i$ 怎么求 $S_{i,p_i}$。令 $x_i\oplus p_i$ 最高的为 $1$ 的位为 $a_i$，那么若 $x_i$ 在这一位上为 $0$，则显然 $p_i>x_i$，$S_{i,p_i}=0$（这也会使得后面的 $\prod$ 为 $0$）。否则容易发现 $S_{i,p_i}$ 的值为生成序列时 $\operatorname{lowbit}(x)=2^{a_i}$ 时，对应的 $x\times(x\oplus v)$。

现在就可以尝试解决询问了。注意到如果 $\max a_i$ 要小于 $d\oplus\bigoplus_{i\le c}x_i$ 的最高位的 $1$ 的位置，那么这个位置上就一定不满足 $d$ 的条件。这启示我们关注 $\max a_i$。

然后就能发现一个非常厉害的性质：当我们确定了 $\max a_i$ 及对应的 $i$ 之后，由于此时 $S_{i,p_i}$ 已经确定了，就能如上文，$a_i$ 之后的位可以先把其它的都确定了，再用 $p_i$ 满足 $d$ 的限制。而又知道 $a_i$ 之前的位，$p_i$ 都是和 $x_i$ 相同的，那么就只需要使 $a_i$ 这一位满足 $d$ 的限制就行了。

于是考虑预处理 $f_{l,r,i,0/1}$ 表示 $[l,r]$ 内的序列，$\max a_j=i$，并且选了奇数/偶数个 $a_j=i$ 的位置的方案数。转移懒得说，反正好推并且还不是正解。那么询问就可以枚举第一个 $\max a_i$ 的位置，答案即为 $\sum_{i\le c}\sum_j \sum_{k<j}f_{1,i-1,k,0/1}\times f_{i,c,j,0/1}$，$0/1$ 要根据 $j$ 和上面最高位 $1$ 的位置判断。最后可以做到 $O((n+q)n\log V)$。

考虑优化，发现枚举这个 $\max a_i$ 的位置没有意义，不如从前往后推，维护 $f_{i,0/1}$ 表示 $\max a_j=i$ 且其数量为奇数/偶数的方案数。考虑往后面加入一个序列，$f$ 怎么变化。设 $g_i$ 表示 $a_j=i$ 时的所有方案之和，那么转移即为 $f_{i,0}\leftarrow f_{i,0}\times \sum_{j<i}g_j+f_{i,1}\times g_i,f_{i,1}\leftarrow f_{i,1}\times \sum_{j<i}g_j+f_{i,0}\times g_i$。此外还要加上 $\max a_i$ 在这一位的贡献，即为前面所有序列的 $\prod\sum_{j<i}g_j$ 再乘上这里的 $\frac{g_i}{2^i}$。最后统计答案也是简单的。复杂度 $O((n+q)\log V)$。

2.20-T2 double $\color{blue}\Diamond$

容易发现算 $E(c_i)$ 不如算 $E(b_i)$ 再前缀和。$\color{blue}\Diamond$ 算 $E(b_i)$ 一个主要问题是排序，那么考虑经典套路 $E(x)=\sum_iP(x\ge i)$，于是变成算 $\sum_jP(b_i\ge j)$。又有 $P(b_i\ge j)=P(\sum[b_i\ge j]\ge n-i+1)$，于是要算的就是有至少 $n-i+1$ 个 $b_i\ge j$ 的方案数。（这个可以直接在排序前的 $b_i$ 算）

考虑这个怎么算。至少是难算的，但是可以变成恰好，恰好又能从钦定过来。于是先算钦定有 $i$ 个 $b_i\ge j$ 的方案数，这里不同的钦定算不同的方案。这个可以插板，令其为 $f_{i,j}=\binom ni\times\binom{m-(j-1)\times i}n$。然后可以 $n^2$ 二项式反演得到恰好的 $g_{i,j}$，再后缀和就能得到至少的 $h_{i,j}$ 了。

但是这个复杂度大概是 $n^3$ 的，不能接受。不过注意到二项式反演和后缀和的转移和系数之类，包括最后的答案都之和 $i$ 有关，于是直接把所有 $j$ 并起来一起做，就能 $O(n^2+m\log m)$ 解决了。

2.21-T1 thefall $\color{blue}\Diamond$

我觉得这个题很有意思啊！

首先不难发现弱点击破之后一定会不断用 $\max b$ 打直到击败，所以只关心击破时的选择。先考虑一个暴力的 $O(nc^2)$ dp：设 $dp_{i,j}$ 表示当前削韧值和为 $i$，已经攻击了 $j$ 次的最大消耗血量，背包转移即可。

然后非常有意思的是，$\color{blue}\Diamond$ 为了简化这个状态，可以考虑把已经攻击的 $j$ 次算到后面的 $\max b$ 头上，这样就能将一次攻击转化成消耗血量 $-\max b_i$，从而去掉一维，变成 $O(nc)$ 了。

2.21-T2 cruising

看到这个加删边操作，首先可能想到线段树分治。但是这样很难处理询问，除了线段树分治又没有什么方便解决这个问题的方法。怎么办！观察到数据范围 $10^5$，那就暴力一点，直接对 $m$ 操作分块！

然后发现要对于点编号轴上的前后缀维护并查集，每次暴力枚举 $O(B)$ 条边合并后处理询问再撤销。这可以直接用可持久化并查集实现，但是太粪了并且两个 $\log$。怎么办！发现可以再离线下来扫描线，动态维护当前前缀并查集，就能 $O((n+q)\sqrt m\log n)$ 了！

然后去掉 $\log$ 也是简单的。容易发现固定一段前缀的并查集后，实际上可能合并的点只有 $O(B)$ 个，所以直接新开一个并查集直接维护，就不用撤销了。