task11

[TOC]

1. CF1329E - Dreamoon Loves AA [E]

题面

给定 $n,m,k$，有一个下标为 $0\sim n$ 的 AB 串 $s$，其中 $s_0$ 和 $s_n$ 必定为 A，另外有 $k$ 个位置为 A

你需要选择恰好 $k$ 个 B 变为 A，使得更改完之后相邻两个 A 之间的距离的极差最小，求最小极差

$1\le n\le10^{15},0\le m\le4\times10^5,0\le k<n-m$

题解

Sol

考虑对一个 $[l,r]$ 判断是否可能，那么相当于对于每个 $i$，需要满足 $lx_i\le a_i\le rx_i$，且 $\sum x=k+m+1$

令 $k\leftarrow k+m+1$，变形为 $\lceil\frac{a_i}r\rceil\le x_i\le\lfloor\frac{a_i}l\rfloor$，那么我们可以根据这个二分得出一个 $l$ 的上界，以及一个 $r$ 的下界

问题是有可能出现 $\lceil\frac{a_i}r\rceil>\lfloor\frac{a_i}l\rfloor$，那么我们需要将 $r$ 调大或者 $l$ 调小

每个这样的限制可以重述为 $l\le x$ 或 $r\ge y$，那么我们显然是取 $l$ 较松的一个前缀，其余都取 $r$，直接枚举即可

复杂度 $O(m\log n)$

2. ARC159E - Difference Sum Query [K]

题面

给定 $n,m$，以及 $m$ 个二元组 $(a_i,b_i)$：

定义 $x_i$ 如下过程的循环次数：

初始 $L\leftarrow1,R\leftarrow n,t\leftarrow0$
令 $M\leftarrow\left\lfloor\dfrac{a_iL+b_iR}{a_i+b_i}\right\rfloor$
若 $iM$，则令 $L\leftarrow M+1$

$q$ 次询问，每次给定 $c_i,d_i$，求 $\sum_{i=c_i}^{d_i-1}|x_i-x_{i+1}|$

$2\le n\le10^{15},1\le m\le100,1\le a_i,b_i\le1000,1\le q\le10^4,\max(\frac{a_i}{b_i},\frac{b_i}{a_i})\le2$

题解

Sol

考虑这棵树的中序遍历为 $1,2,\cdots,n$，也就是说 $i-1$ 和 $i$ 一定是祖孙关系，那么 $|x_i-x_{i+1}|$ 就是树上两点的距离，那么我们要求的就是区间虚树大小

对两个端点分别在树上搜索，剩下的事情是容易计算的，复杂度 $O(q\log n)$

3. CF1924E - Paper Cutting Again [E]

题面

给定 $n\times m$ 的方格纸，每次选择从当前的 $n+m-2$ 条横竖直线里选择一条剪开，将剪出来右边或下边的部分扔掉

问期望多少次操作后纸的面积 $<k$

$1\le n,m\le10^6,2\le k\le10^{12}$

题解

Sol

Flamire 做法

将随机过程视作：每次随机从所有的 $n+m-2$ 条直线中选择一条，如果已经被剪过则不计入贡献

考虑一条竖线产生贡献的概率（横线同理），我们可以将这个过程看作方格纸右下角的移动，其就是竖线右侧每个使面积 $\ge k$ 的右下角出现的概率，乘上 $\frac1{n+m-2}$

定义 $f(x,y)$ 表示一个点 $(x,y)$ 出现的概率，我们可以枚举出现在第几次操作，令 $g(x,y,i)$ 表示一个点 $(x,y)$ 在第 $i$ 次操作后出现的概率，则 $g(x,y,i)=\left(\dfrac{n-x+m-y}{n+m-2}\right)^i-2\left(\dfrac{n-x+m-y-1}{n+m-2}\right)^i-\left(\dfrac{n-x+m-y-2}{n+m-2}\right)^i$，可能需要特判 $x=n$ 与 $y=m$ 的情况，那么 $f$ 就可以通过等比数列求和求出

注意到 $f$ 的值只和 $x+y$ 有关，而每一列的点的 $x+y$ 是一个区间，因此我们可以处理一些前缀和，得到每条竖线的值右边区域的 $f$ 之和

复杂度 $O(n+m)$

题解做法

将随机过程视作：随机一个 $n+m-2$ 条直线的排列，依次剪每条直线，如果已经被剪过则不计入次数

我们把最后一次操作扔掉，对每条直线算切完之后仍然 $\ge k$ 的概率

对于一条竖线 $x=i$，满足条件的要求即为它在所有 $x=j(j<i)$ 之前，以及在所有 $y=j(j<\lfloor\frac ki\rfloor)$ 之前，这是一个自然数的倒数，容易 $O(n+m)$ 计算

4. CF1975G - Zimpha Fan Club [E] ⭐

题面

给定两个含有小写字母，*，- 的字符串 $s,t$

一个 - 可以和任意字符匹配，一个 * 可以和任意零个或多个字符匹配，问两个串是否能匹配

$1\le |s|,|t|\le2\times10^6$，12s

题解

Sol

只有 - 的字符串匹配是经典 fft，因此我们可以先排除字符串算法（

考虑 * 产生的影响，首先判掉没有 * 的前缀和后缀，它们必须对位匹配

如果前缀的第一个 * 在 $s$，后缀的第一个 * 在 $t$，那么不难发现这两个串一定能匹配，反过来同理

那么两个 * 都必须在一侧，假设在 $s$，此时如果 $t$ 内部还有 *，不难发现这两个串也一定能匹配

因此只用考虑 $t$ 没有 * 的情况，那么 $s$ 会被 * 拆成若干连续段，我们要判断这些连续段是否能依次匹配到 $t$ 中

一种显然的想法是首先找到第一个段的首次出现位置，然后找到第二个段在后面首次出现位置，一直找下去，但是如果每次对整个串做判断复杂度会很高

因此我们每次匹配一个段 $s_i$ 时，将当前 $t$ 的前 $2|s_i|$ 个字符拿出来匹配，如果匹配不上我们可以删除 $|s_i|$ 个字符，每个段最多匹配上一次，所以我们的总复杂度是 $O(n\log n)$

5. CF1975H - 378QAQ and Core [E]

题面

给定长为 $n$ 的小写字符串，重排这个字符串使得字典序最大的后缀最小

$1\le n\le10^6$

题解

Sol

这不是我们集训队互测吗。

不会证明。懒得证明。

考虑最大的若干字符，最后的最大后缀一定是这些字符代表的后缀之一，如 aaaaabbbbcccccccddddd，那么我们首先可以将一个 d 放在最后，去除它的影响

至于为什么这么做是对的：如果最后一个字符不是 d，我们把最后一个 d 后面的所有东西扔到某一个 d 前面，一定会让最后一个 d，以及前面的 d 的字典序都变小

接下来剩下的 d 需要都与 a 结合，那么我们就有了 4 个 da

继续结合，a 不够用了，我们产出 1 个 daa 和 3 个 dab

此时 daa 不可能是最大的后缀了，因此我们只用继续给 dab 加字符，得到 1 个 dabb 和 2 个 dabc

继续加完 c，得到 2 个 dabccc，列出此时的所有字符串：c,d-,daa,dabb,dabccc,dabccc

我们发现，每一轮对于每个最大值，直接在末尾添加当前最小的字符串就是对的

即使范围有重叠也是对的，很神奇吧。

按照这个写一下，用哈希比较字符串，就可以得到一个 $O(n)$ 做法

6. THUPC2024 Final A - 古明地枣的袜子 [K] ✔️

题面

有数组 $a_1,a_2,\cdots,a_n$，以及 $n$ 次前缀加操作，第 $i$ 次给 $a[1:x_i]$ 整体 $+y_i$

$q$ 次询问，每次给定 $[l,r]$，询问只保留第 $l$ 次到第 $r$ 次内的操作，$a$ 初值全 $0$，求操作完后 $\max_{i=1}^na_i$ 的值

$1\le n,q\le5\times10^5,|y_i|\le n$，10s

题解

Sol

看起来不好 polylog，考虑根号。

对 $a$ 分块，那么我们对于属于这个块的操作计算一下答案，将包含这个块的操作的值再加上即可

但是属于一个块的操作依然有可能有很多，我们对操作进行一些扰动，使得每个位置恰好被操作一次，这会导致我们有些下标的值不应该被计入答案，不过这是容易处理的

那么现在我们大小为 $B$ 的块只有 $B$ 次操作，我们可以枚举询问区间，是 $O(B^2)$ 的，如果我们可以在 $O(B^2)$ 的复杂度内算出一个块所有区间的答案，最后复杂度就是 $O(n\sqrt n)$ 的

直接用线段树之类的需要带一个 log，考虑如何不带 log

我们对 $a$ 的下标进行分治，对于区间 $[l,r]$，我们只需要保留 $O((r-l)^2)$ 种答案，容易支持 $[l,m]$ 和 $[m+1,r]$ 合并到 $[l,r]$，复杂度 $T(n)=2T(\frac n2)+O(n^2)$，解得 $T(n)=O(n^2)$，那么对于一个块我们的复杂度就是 $O(B^2)$ 的

总复杂度 $O(n\sqrt n)$

7. CF1119H - Triple [E]

题面

给定 $n$ 组 $[0,2^k-1]$ 内的正整数 $\{a_i,b_i,c_i\}$，你需要从每组中选一个数

每组中选择 $a_i,b_i,c_i$ 的方案数分别为 $x,y,z$，其中 $x,y,z$ 为三个固定的常数，对所有 $n$ 组均一致

对每个 $t=0,1,\cdots,2^k-1$，求选出的数异或为 $t$ 的方案数，对 $998244353$ 取模

$1\le n\le10^5,1\le k\le17$

题解

Sol

Flamire 做法

先异或 $a_i$，这样我们的一个数就变成 $0$ 了，方便处理

我们要求的就是 $\prod(x+yw^{b_i}+zw^{c_i})$，其中 $\prod$ 为形式幂级数的异或卷积

注意到只有 $(x+yw^{b_i})$，那么我们可以做一个类似于高维前缀和的东西将最后做完 fwtxor 变换的东西求出来，ifwt 回去就可以得到答案

那么我们考虑将 $(x+yw^{b_i}+zw^{c_i})$ 分解为一些两项的形式，考虑使用 $FWT(f)_S=\sum_T(-1)^{|S\cap|T}f_T$，我们随便设一些操作，然后高斯消元一下，得到：

设 $v_{ij}$ 表示与 $b$ 交的大小奇偶性为 $i$，与 $c$ 交的大小奇偶性为 $j$，那么原来三项式进行 fwt 变换等价于对初始全 $1$ 的数组进行如下操作：
将所有数乘上 $v_{00}$
将所有与 $b$ 交为奇数的乘上 $\sqrt{\dfrac{v_{10}v_{11}}{v_{00}v_{01}}}$
将所有与 $c$ 交为奇数的乘上 $\sqrt{\dfrac{v_{01}v_{11}}{v_{00}v_{10}}}$
将所有与 $b\oplus c$ 交为奇数的乘上 $\sqrt{\dfrac{v_{01}v_{10}}{v_{00}v_{11}}}$

这道题的 $v_{ij}$ 都是固定的，因此直接维护系数即可，复杂度 $O(n+2^kk)$

题解做法

最后的每一个位置是若干 $x+y+z,x+y-z,x-y+z,x-y-z$ 的乘积

考虑设这四项的系数分别为 $X,Y,Z,W$，我们对每个位置需要解出这四个数

首先，有 $X+Y+Z+W=n$

我们将所有幂级数只有 $b_i$ 的位置设成 $1$，那么对于 fwt 后的位置，$X,Y$ 类的位置被贡献了 $1$，$Z,W$ 的位置被贡献了 $-1$，也就是说如果我们将所有 $n$ 个幂级数的 fwt 加起来，我们就得到了 $X+Y-Z-W$，由于 fwt 是线性运算，所以我们只需要将所有幂级数加起来做一次 fwt

通过 $c_i$ 可以得到 $X-Y+Z-W$

通过 $b_i\oplus c_i$ 可以得到 $X-Y-Z+W$

解一下方程即可求出每一项

复杂度 $O(2^kk)$

8. CF1750G - Doping [E]

题面

给定长为 $n$ 的排列 $p$，对每个 $t=0,1,\cdots,n-1$，求有多少排列 $p^\prime$ 满足：

$p^\prime$ 的字典序小于 $p$
恰好有 $t$ 个 $1\le i<n$ 满足 $p^\prime_i+1=p^\prime_{i+1}$

对给定正整数 $m$ 取模

$1\le n\le2000,10\le m\le10^9$

题解

Sol

首先考虑得到一个 $O(n^3)$ 做法。

如果没有字典序限制的话一种很显然的想法就是钦定，那么我们现在枚举 lcp

设 lcp 为 $i$，现在后缀中我们可以使用一个集合内的数，我们需要算钦定 $j$ 个位置满足 $p^\prime_i+1=p^\prime_{i+1}$ 的方案数 $f_{i,j}$

直接计算不好算，因此我们不直接钦定位置，而是钦定一些值域段，然后将它们排进去，进行一些分类讨论可以得到一个对每个 $i$ 都为 $O(n^2)$ 的求解方式，优化一下即可变成 $O(n)$

现在的复杂度瓶颈在于我们需要对每个 $i$ 都做一次二项式反演

注意到我们在 $f_i$ 的时候没有钦定前面的位置，因此我们可以倒着 dp，给这些已知的位置也加上钦定，那么我们就只用做一次二项式反演即可

复杂度 $O(n^2)$

9. CF1129E - Legendary Tree [E]

题面

交互题。

有一棵隐藏的 $n$ 个节点的树。你可以进行 $11111$ 次询问，每次询问你需要给出两个不交的集合 $S,T$，以及一个节点 $v$，交互库会回答有多少对 $s\in S,t\in T$ 使得 $s$ 到 $t$ 的路径经过 $v$

$2\le n\le500$

题解

Sol

我们可以询问 $(\{1\},\{2,3,\cdots,n\},i)$ 得到 $i$ 的子树大小，那么按照子树大小从大到小排序，我们就得到了这棵树的一个拓扑序

正着直接做需要乱七八糟的点分治。

考虑倒着扫，那么当前后面的结构会形成若干棵子树，设这些子树的根组成的数组为 $o$，那么询问 $(\{1\},o[L:R],i)$ 就可以得到区间中是否有 $i$ 的儿子，那么我们类似于线段树/二分，每个儿子最多贡献 $O(\log n)$ 次询问，之后这个儿子就会被从 $o$ 中删除，因此总询问次数为 $O(n\log n)$

10. JOISC2017 - 开荒者 [K] ✔️

题面

一个 $R\times C$ 的网格，有 $n$ 个给定格子有草

每年夏天，你可以选择一个方向，让所有草向这个方向扩散一格（之前的草仍被保留）

求最少多少年能让网格填满草

$1\le n\le300,1\le R,C\le10^9$

题解

Sol

注意到操作的顺序无关，最后每个草都会被扩展成一个矩形，设上下左右操作次数分别为 $u,d,l,r$

注意到如果 $u+d,l+r$ 均相等，那么扩散出的图形形状应该是一样的，只不过位置可能不同

我们期望让这个东西和值域无关，因此我们需要进行一些分析

也就是说总共只有 $O(n^2)$ 种可能的 $u+d$

此时一种可行的写法是枚举 $u+d$，二分 $l+r$，然后直接判断产生的图形是否能包含一个 $R\times C$ 的矩形，复杂度 $O(n^3\log n)$

但是其实可以不带 log。

对于固定的 $u+d$，我们首先假设 $u=0$，每一行会被哪些草影响到已经固定，那么对于一行，设上面的草为 $i_1,i_2,\cdots,i_k$，那么如果最后 $R\times C$ 的矩形包含它，意味着需要满足 $l\ge i_1-1,l+r\ge i_{j+1}-i_j-1,r\ge C-i_k$

我们按顺序扫这些行，做三个滑动窗口，就可以得到把 $R\times C$ 矩形放在每一个位置的限制

但是还有未解决的问题：

对于一行，计算最大的相邻差直接 $O(n)$ 会导致复杂度变为 $O(n^4)$，注意到影响到一行的草一定是按 $x$ 排序后的一个区间，因此我们只用预处理 $O(n^2)$ 个区间，容易做到 $O(n^3)$
我们进行扫描线需要将操作排序，这个如果我们一开始将所有草按 $x$ 排序，就是两个有序序列的归并，因此也不需要带 log

那么我们就得到了一个 $O(n^3)$ 做法

至于为什么选出一个 $R\times C$ 矩形一定意味着找到了答案，不妨假设我们此时固定了 $u+d,l,r$

找到 $x$ 最小的草 $G$，如果 $R\times C$ 矩形与 $G$ 产生出的矩形不交，那么由于一开始所有草都在 $R\times C$ 矩形内，因此这个矩形内的有草行数一定 $<R$，不合法

我们将草整体平移，将 $G$ 平移到 $R\times C$ 与 $G$ 的矩形第一次有交的行，每个草依然在原来的矩形内，并且每个草也在 $R\times C$ 矩形的范围内，因此构造合法

11. JOISC2017 - 港口设施 [S]

题面

有 $n$ 个物品和两个栈，每个物品被压入某个栈一次，弹出某个栈一次

给出每个物品被压入和弹出的时刻，保证为 $1\sim 2n$ 的排列

求有多少种选择每个物品压入哪个栈的方案，使得入栈出栈顺序合法，对 $10^9+7$ 取模

$1\le n\le10^6$

题解

Sol

相当于我们在所有相交不包含的区间之间连边，判断是否有奇环，并且求连通块个数

相交不包含，这个我们可以用一个类似栈的结构去刻画，那么我们每次对于一个区间的 merge 就是把一段区间内的点全 merge 起来，这个可以用并查集维护

复杂度 $O(n\alpha(n))$

12. JOISC2017 - 烟花棒 [E]

题面

有 $n$ 个人在数轴上，第 $i$ 个人的位置为 $x_i$，保证 $x$ 递增，每个人手中有一个烟花，每个烟花能燃烧 $T$ 的时间

初始第 $k$ 个人的烟花刚刚被点燃，每个人的最大速度为 $v$，这些人会在数轴上运动，当两个人位置相同时，可以将未点燃的烟花用燃烧着的烟花点燃

求想让所有人的烟花都被点燃过，$v$ 最小应该是多少

$1\le n,k\le10^5$

题解

Sol

首先，可以二分，那么变成判定性问题。

一个显然的事情就是两边的人一定向中间运动。

进一步，我们可以发现一个人到达 $k$ 的位置后，可以让他跟着 $k$ 走，给 $k$ 的烟花续命

可以说明，如果两个人相遇，将烟花点燃后分开一定不优，因为 $k$ 向一边走，另一边一定跟着 $k$ 走，那么它们之间的距离都不会发生改变，也就是说点燃后分开产生的效果可以被不分开所替代

那么现在问题就转化为，$k$ 一开始有 $2vT$ 的距离可以走，每一步可以耗费一些距离，选择吃掉左边或者右边的人，得到 $2vT$ 的距离，求是否能吃掉所有人

计算出来所有收益，从 $k$ 开始向左吃，如果吃到一段之后收益是正的了，那么只要我们某一时刻能吃掉这一段，吃掉了一定不劣，对于右边的段同理

那么我们每次求出左边和右边的段，每次判断是否能吃掉一个段，能吃就吃掉，否则无解

最后的结果就是两边继续吃下去收益都是负的

这种情况下我们从最后的情况出发，从两边向内走，那么此时就和吃人一样了，也就是说我们把刚才的事情倒过来做一遍就可以了

复杂度 $O(n\log V)$

13. JOISC2017 - 门票安排 [E] ⭐

题面

环上有 $n$ 个点，有 $m$ 组人，第 $i$ 组人有 $c_i$ 个要从 $a_i$ 走到 $b_i$，这些人可以选择两条路中的一条，他们不一定要选择同一条。

这 $n$ 个点之间的 $n$ 条线段，每条会被若干人经过，求这些线段中，经过人数最大值的最小值。

$1\le n\le2\times10^5,1\le m\le10^5,1\le c_i\le10^9$

题解

Sol

环上不好考虑，从 $1-n$ 断开扔到直线上

我们先假设所有人选的都是区间，那么改成区间的补会让内部 $-1$，外部 $+1$，这个很丑，所以改成整体 $+1$，内部 $-2$

那么这个问题瞬间就好做了：我们假设一共用了 $M$ 个补，那么相当于我们可以选择 $M$ 个区间 $-2$，最大值最小

反过来，相当于我们固定一个最大值 $M$，那么我们需要选择尽量少的 $-2$ 操作，使得最大值 $\le M$

这个非常贪心，我们从左到右扫，如果当前位置 $>M$ 就选择右端点最大的区间操作

那么对于所有最大值把答案 $+M$ 取 min 就是最终的答案了。

注意到对于 $M$ 的同一奇偶，这个东西是凸的，那么加一个二分即可，复杂度 $O(n\log n\log V)$

至于为什么是凸的。我不会证。但是大致的直觉是：$x$ 到 $x+2$ 的影响是相当于一些位置需要被覆盖的次数 $+1$，而 $x+2$ 到 $x+4$ 的时候 $+1$ 的位置是 $x$ 到 $x+2$ 时的超集，并且能选择的区间越来越少，所以差分越来越大

14. JOISC2017 - 火车旅行 [S]

题面

数轴上有 $n$ 个点，第 $i$ 个点的高度为 $a_i\in[1,k]$，保证 $a_1=a_n=k$

假设你当前在 $x$，每步你可以选定一个值 $v$，然后移动到 $x$ 左边或右边第一个 $\ge v$ 的下标

$q$ 次询问，每次给定一个起点和终点，求两点间最短路

$2\le n\le10^5$

题解

Sol

Flamire 做法

考虑最值分治：找到当前区间内最大的 $a_i$，对于两边的每个点，维护 $f_i$ 表示从 $i$ 到区间左边的最短路，$g_i$ 表示 $i$ 到区间右边的最短路，合并两个区间时我们需要进行的就是一个 2x2 的区间 $(min,+)$ 矩乘，用线段树维护即可，复杂度 $O(n\log n)$

题解做法

考虑倍增：容易发现起点和终点只要都到达中间的最大值即可

那么我们倍增维护出起点和终点分别跳 $2^j$ 步后能到区间即可

复杂度 $O(n\log n)$

15. CF1909I - Short Permutation Problem [K]

题面

给定 $n$，对每对 $m,k(3\le m\le n+1,0\le k<n)$，求出有多少排列 $p$ 满足 $p_i+p_{i+1}\ge m$ 的个数恰好为 $k$，对 $998244353$ 取模

$1\le n\le4000$

题解

Sol

经典套路，转化成逐个加数，按 $[m/2,m/2+1,m/2-1,m/2+2,\cdots]$ 的顺序加数，容易发现每个数旁边的两个只和新加的数的类型有关

令 $dp_{i,j}$ 表示当前加入了前 $i$ 个数，有 $j$ 对合法相邻元素，转移是容易的，我们得到了一个 $O(n^3)$ 的做法

我们转化成 $\le m$ 考虑，这样对于每个 $m$ 我们加入的数一定先是大小交错，后全是大数，前面的部分对于所有 $m$ 都是一样的，后面的大数部分可以写成组合数的形式，然后使用 ntt 优化，复杂度 $O(n^2\log n)$

16. CF1909H - Parallel Swaps Sort [E]

题面

给定 $1\sim n$ 的排列 $a_1,a_2,\cdots,a_n$，你需要进行如下操作若干次，将 $a$ 排序：

选定区间长度为偶数的区间 $[l,r]$，交换 $(a_l,a_{l+1}),(a_{l+2},a_{l+3}),\cdots,(a_{r-1},a_r)$

你最多进行 $10^6$，请构造一种操作序列

$1\le n\le3\times10^5$

题解

Sol

Flamire 做法

经过若干次手模，可以发现每次好像换最前面的一段都满足 $a_i>a_{i+1}$ 的区间很优

我们规范一下这个过程，维护一个前缀 $I$，$I$ 不断变长，每次新加进来一个数将其查到前面有序的位置中

16 3 4 11 12 6 5 15 10 8 14 13 1 2 9 7
3 16 4 11 12 6 5 15 10 8 14 13 1 2 9 7
3 4 16 11 12 6 5 15 10 8 14 13 1 2 9 7
3 4 11 16 12 6 5 15 10 8 14 13 1 2 9 7
3 4 11 12 16 6 5 15 10 8 14 13 1 2 9 7
3 4 11 12 6 16 5 15 10 8 14 13 1 2 9 7
3 4 11 6 12 5 16 15 10 8 14 13 1 2 9 7
3 4 6 11 5 12 15 16 10 8 14 13 1 2 9 7
3 4 6 11 5 12 15 10 16 8 14 13 1 2 9 7
3 4 6 11 5 12 10 15 8 16 14 13 1 2 9 7
3 4 6 5 11 10 12 8 15 14 16 13 1 2 9 7
3 4 5 6 10 11 8 12 14 15 13 16 1 2 9 7
3 4 5 6 10 11 8 12 14 13 15 1 16 2 9 7
3 4 5 6 10 11 8 12 13 14 1 15 2 16 9 7
3 4 5 6 10 11 8 12 13 1 14 2 15 9 16 7
3 4 5 6 10 11 8 12 1 13 2 14 9 15 7 16
3 4 5 6 10 8 11 1 12 2 13 9 14 7 15 16
3 4 5 6 8 10 1 11 2 12 9 13 7 14 15 16
3 4 5 6 8 1 10 2 11 9 12 7 13 14 15 16
3 4 5 6 1 8 2 10 9 11 7 12 13 14 15 16
3 4 5 1 6 2 8 9 10 7 11 12 13 14 15 16
3 4 5 1 6 2 8 9 7 10 11 12 13 14 15 16
3 4 5 1 6 2 8 7 9 10 11 12 13 14 15 16
3 4 1 5 2 6 7 8 9 10 11 12 13 14 15 16
3 1 4 2 5 6 7 8 9 10 11 12 13 14 15 16
1 3 2 4 5 6 7 8 9 10 11 12 13 14 15 16
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

用平衡树维护每个数到达有序位置的时间

复杂度 $O(n\log n)$

zak 做法

考虑反转排列的操作：这个是容易构造的，不断操作 $(1,n)$ 和 $(2,n-1)$ （或 $(1,n-1)$ 和 $(2,n)$）

反转排列的操作中，每对数恰好相邻了一次，那么我们在这时交换两个数，它们最后到的位置也会交换，相当于我们以某种顺序给定了这 $\frac12n(n-1)$ 个数对，每一步可以选择是否交换它们

而我们是可以交换出任意排列的，如果两个相邻数属于同一个置换环就交换，最后任意两个都不属于同一个置换环，因此可以得到 $1,2,\cdots,n$，并且生效的操作数最多 $n-1$ 次

那么我们就得到了一个 $O(n^2)$，操作次数 $2n-1$ 的做法，考虑优化

应该观察一下矩阵的性质啥的？？我不知道啊。总之似乎是可以维护的

17. CF1965F - Conference [K] ⭐

题面

有 $n$ 个人，第 $i$ 个人可以安排在第 $[l_i,r_i]$ 天演讲

你需要选择 $k$ 个连续的天，使得存在一种将人和天的匹配方式，使得每个天都被匹配上

对 $k=1,2,\cdots,n$，求有多少选择连续 $k$ 天的方式满足条件

$1\le n\le2\times10^5,1\le l_i,r_i\le2\times 10^5$

题解

Sol

首先，这个问题可以 two-pointers，那么我们需要解决的问题就是如何判断一个区间是否合法

这是一个区间图匹配问题，贪心方法显然不好扩展，因此考虑 Hall 定理

由于天数是完美匹配，所以我们可以考虑以人为 $N(S)$，以区间为 $S$，一种简单的想法是只考虑 $S$ 为区间的情况，但这是错误的，反例容易构造

考虑观察一些性质：对于两个人 $[a,b],[a,c]$，其中 $a\le b\le c$，那么我们把 $[a,c]$ 改为 $[a+1,c]$ 并不会影响答案，如果调整出空区间就将这个人扔掉

注意到这样调整之后所有人的 $l$ 一定互不相同，可以发现（？）现在我们只考虑所有 $S$ 为区间的情况就够了，因为如果 $x,y\in S,[x+1,y-1]\not\in S$，那么加上 $[x+1,y-1]$ 中的所有元素后，$|N(S)|$ 的增加量一定小于等于 $S$ 的增加量

但是所有区间还不是很好判，继续观察性质：我们对右端点 $r$ 做同样的处理，而 $r$ 互不相同的情况下，如果 $[l,r]$ 非法，那么 $[l-1,r]$ 和 $[l,r+1]$ 一定也非法

考虑 $l$ 扩展到 $l-1$ 发生的事情：$|N(S)|$ 增加量 $\le 1$，$|S|$ 增加量 $=1$

那么相当于我们只用判整个区间是否合法，two-pointers $O(n)$ 维护即可

18. CF1930G - Prefix Max Set Counting [E] ⭐

题面

给定一棵根为 $1$ 的 $n$ 个点的树

求所有 dfs 序能生成的编号前缀最大值集合的数量，对 $998244353$ 取模

$1\le n\le10^6$

题解

Sol

考虑一个点的所有儿子，不妨将其按子树最大值 $mx$ 排序

注意到如果我们先访问了 $mx_{v2}>mx_{v1}$，那么 $v1$ 一定不会再对答案造成贡献了，这意味着我们可以将这个过程视作选择一些 $mx$ 递增的子树访问（最大的子树必须选），剩下的丢弃掉

再进行一些观察：如果访问子树 $v$ 的时候，前面的最大值 $>mx_v$，那么 $v$ 一定不会有任何作用，否则出这个子树的时候前面的最大值一定为 $mx_v$

现在访问顺序固定了，那么我们可以进行一个过程，不断计算出到一个点 $u$ 之前最大值为 $j$ 的路径为多少，搜进一棵子树的时候，这棵子树要么不选，要么会把所有 $<mx_v$ 的值全贡献到 $mx_v$，也就是说最后的结果就是 $mx_u$ 的位置上加上了某个值

在进入一个节点 $u$ 时我们需要将前缀的值全部赋 $0$，然后单点加到某一个点上，再对每个子树对应的位置上加上值，最后比较一下 $mx_u$ 位置的值和一开始的值，然后将所有操作撤回

注意到全部赋 $0$ 操作后赋 $0$ 的区间不会再被使用，所以我们其实根本不用赋 $0$，那么剩下的部分用树状数组维护即可

复杂度 $O(n\log n)$

19. CF1817F - Entangled Substrings [E]

题面

给定一个字符串 $s$，求非空子串对 $(a,b)$ 的对数，满足存在一个字符串（可空）$c$ 使得 $a,b$ 所有在 $s$ 中的出现都形如 $acb$

$1\le|s|\le10^5$

题解

Sol

题解有厉害基本子串结构，但是我不会。

不过这是纯纯的唐氏题。

考虑用熟悉的事情改写 $(a,b)$ 的限制，注意到 $a,b,c$ endpos 差分都必须相同，且 $b,c$ 属于同一个 sam 节点

endpos 差分可以用哈希判，因此我们只用考虑一个等价类内的 sam 节点。

对于一个 $b,c$ 的 sam 节点 $u$，考虑如何计数 $(a,b,c)$ 对数，设串 $x$ 的第一次出现位置为 $[l(x),r(x)]$，那么需要满足的是 $l(a)=l(c),r(a)<l(b)$

那么我们如果固定 $a,u$，$c$ 也只有一种选法，而 $b$ 只要满足左端点比 $r(a)$ 靠后，也就是 $r(a)$ 到 $mn(u)-len(fail(u))+1$ 的距离种选法

也就是说，对于第一次出现在 $[mn(u)-len(u)+1,mn(u)-len(fail(u))]$ 内的所有串 $a$，它会贡献到右端点距离的方案数，这可以用线段树+扫描线维护

复杂度 $O(n\log n)$

20. CF1738H - Palindrome Addict [E]

题面

你有一个字符串 $s$，初始为空，有 $q$ 次操作：

push c，在 $s$ 末尾接上一个字符 $c$
pop，删除 $s$ 的第一个字符

每次操作后求 $s$ 的本质不同回文子串个数

$1\le q\le10^6$

题解

Sol

Flamire 做法

建 PAM，注意到每次 push 和 pop 分别会让一些回文串的出现次数 +1/-1，并且操作的范围都是某个节点的到根链

这个节点可以用倍增求出，用 ds 维护可以做到 $O(q\log^2q)$ 或 $O(q\log q)$

题解做法

考虑发现一些性质：每次加入一个字符或删除一个字符，最多导致本质回文子串个数变化 1，因此可以考虑一些均摊复杂度的做法

加入一个字符的时候判断是否出现新的回文子串是容易的，只要检查一下右端点指针指向的节点是否出现过即可

那么我们只需要找到需要被删除的节点，就可以在此基础上解决这个问题

直接找到比较困难，因此我们考虑维护所有已经出现的串的最右出现位置 $pos$，那么所有 $L=i$ 的串会在删除 $s_i$ 的时候消失掉，我们对每个 $L$ 开一个 vector $v_L$，记录左端点为 $L$ 的串，加入一个字符时更新到根链上的所有串的 $pos$，并 $pos-len+1$ 处记录每个串，那么我们从左扫到这个位置时只需要遍历 $v_i$ 内的元素即可

但是暴力更新复杂度是错的，因此我们采用懒标记的方式：当一个点被删除时，将节点上的 $pos$ 标记上传给父亲，同时我们并没有必要从 $v_L$ 中移除元素，只要判断一下当前 $v_L$ 中的串是否可以被删除即可

注意到有可能出现儿子的 $pos$ 还没有传上来的情况，这种情况下当前串一定不能删除，因此我们需要额外记录一个 $deg_u$，表示 $u$ 有多少儿子没有被删除

复杂度 $O(q)$

21. AT_dwacon5th_prelims_e Cyclic GCDs [E]

题面

给定长为 $n$ 的序列 $a_1,a_2,\cdots,a_n$，对于一个 $1\sim n$ 的排列 $p$，定义其权值为每个环上的 $a$ 值最小值的乘积

定义 $w_i$ 为所有有 $i$ 个环的 $1\sim n$ 排列的 $f(p)$ 之和，求 $\gcd(w_1,w_2,\cdots,w_n)$，对 $998244353$ 取模

$1\le n\le10^5,1\le a_i\le10^9$

题解

Sol

注意到可以有一个 dp 解法算所有的 $w_i$：令 $dp_{i,j}$ 表示插入了前 $i$ 小的数，现在形成了 $j$ 个环，转移是 $a_{i+1}\times dp_{i,j}\rightarrow dp_{i+1,j+1}$ 和 $i\times dp_{i,j}\rightarrow dp_{i+1,j}$

也就是说 $w$ 就是 $\prod(a_ix+i-1)$ 的各项系数

打表发现答案看起来像是各种东西乘出来的，大胆猜测一下答案是 $\prod\gcd(a_i,i-1)$，发现对上了

事实上，我们可以证明这件事情：设 $P,Q$ 为两个多项式，且 $c(P),c(Q)$ 表示 $P,Q$ 各项系数的 $\gcd$，那么 $c(P\times Q)=c(P)\times c(Q)$

不妨设 $c(P)=c(Q)=1$，我们证明此时 $c(PQ)=1$ 就相当于证明了原命题

不妨假设某质数 $p$ 满足 $p|c(PQ)$，那么 $P$ 的最高位与 $Q$ 的最高位一定有一个 $p$ 的倍数，不妨设是 $P$ 的最高位，那么我们将 $P$ 的最高位去除，得到 $P^\prime$，$P$ 的最高位对系数产生的贡献一定是 $p$ 的倍数，不影响模 $p$ 的余数，因此 $p|c(P^\prime Q)$ 依然需要成立

最后可以规约到 $P,Q$ 只剩常数项的情况，此时更高次项一定都是 $p$ 的倍数，而 $P,Q$ 的常数项至少有一个是 $p$ 的倍数，矛盾

一种直观的理解方式是 $P,Q$ 在模 $p$ 意义下均非零，而 $PQ$ 在模 $p$ 意义下为 $0$，这个显然不合理

22. CF1394E - Boboniu and Banknote Collection [E] ✔️

题面

给定一个长为 $n$ 的数组 $a_1,a_2,\cdots,a_n$，对每个前缀求最多折多少次（要求对应位置相等）

$1\le n\le10^5,1\le a_i\le n$

题解

Sol

以下均认为回文串指的是偶回文串

对于 $A+\textrm{rev}(A)+A$ 的串，我们称其为 $Z$ 串，那么我们的操作有两种：折掉一个回文前缀/后缀或者折掉一个 $Z$ 串

如果我们一次操作内折掉了一个不是最小的回文前缀/后缀，不难发现这是不优的，因为我们折最小的前后缀可以用更多次操作完成同样的事情，那么这限制我们，每次折的回文串都不能有更短的回文前后缀

如果两个回文串互相覆盖对方的中心，那么一定能产生一个 $Z$ 串，同时这也是 $Z$ 串的充要条件

定义所有不包含 $Z$ 串作为子串的 $Z$ 串为本原 $Z$ 串，那么可以发现本原 $Z$ 串的一定有唯一的回文后缀恰好取在 $\textrm{rev}(A)+A$ 的位置（否则不是本原 $Z$ 串），也就是说最后的方案里 $A$ 和 $\textrm{rev}(A)$ 的内部不会有折叠点

定义 $f(s)$ 为串 $s$ 的答案，那么我们说明 $f(B+A+\text{rev}(A)+A+C)=f(B+A+C)+2$，左边 $\ge$ 右边是好说的，考虑说明左边 $\le$ 右边，考察 $A+\text{rev}(A)+A$ 内部有多少折点

有两个折点，可以直接规约到 $B+A+C$ 的问题，满足条件
没有折点，那么最后操作完的串一定包含 $A+\text{rev}(A)+A$，因此一定可以再接着折，增加操作次数
有一个折点，不妨设是折成 →→← 的样子，那么如果下一段是 ←，我们可以将 →← 段删除，得到一个折点数不变的 $B+A+C$ 的方案，如果下一段是 →，我们可以将 →← 段删除，得到一个折点数 $-2$ 的 $B+A+C$ 的方案

那么也就是说，对于任意一个本原 $Z$ 串，直接将它折掉对答案没有影响。

由于本原 $Z$ 串的性质，加入字符时最多只会产生一个本原 $Z$ 串，该串以新字符为结尾，并且我们直接查询以新字符结尾的最短回文后缀就可以得到该 $Z$ 串的长度，然后再查一下 $i-\frac12len$ 位置的最短回文后缀，判一下长度是否相等即可

那么如果我们能建出 pam，这件事情就是可以办到的。但是最后得到的是一棵字典树，pam 的均摊复杂度不对，这件事情我们稍后处理。

接下来考虑合并回文前缀/后缀的情况。

注意到现在我们的字符串没有本原 $Z$ 串，可以发现我们折的回文串长度一定是单峰的，那么我们拆成两个过程来考虑，一个不断折最短回文前缀，一个不断折最短回文后缀

分析一下，这两个过程大致不会相交，因为我们取出左边最后一个回文串，讨论一下右边第一次跨过来的位置，会发现一定导致两个回文串互相覆盖中心，也就产生了 $Z$ 串，矛盾

唯一相交的情况就是两个过程缩了同一个回文串的两半，比如 1 1 2 3 3 2 1 1 2，这种情况下特判一下就好

对于折后缀，我们在字典树上直接向上指，递推即可

对于折前缀，我们可以维护一个栈，每次新加一个节点的时候判断一下到栈内上一个节点的位置是否是一个回文串，是的话就折掉，回溯的时候只要把范围超掉的弹了就好

那么如果我们能建出 pam，这件事情就是可以办到的。

接下来考虑分析建 pam。

存在不均摊建 pam 的方法，但是我做的时候不会。

考虑观察一下这题的性质：本原 $Z$ 串的限制很苛刻，一个串看起来不能有重复很多次的周期

事实上，我们可以证明，一个回文串的最长回文后缀一定 $\le$ 其长度的 $\frac12$，否则它们会互相覆盖中心，产生 $Z$ 串

那么 pam 的深度是 $O(\log n)$ 的。因此上面那些操作直接暴力，复杂度就是 $O(n\log n)$ 的。

23. CF1098F - Ж-function [K]

题面

给定长为 $n$ 的字符串 $s$，$q$ 次询问，每次询问给定 $l,r$，查询 $\sum_{i=l}^r\text{LCP}(s[l:r],s[i:r])$

$1\le n\le2\times10^5,1\le q\le2\times10^5$

题解

Sol

建 sa，去除一些容易统计的贡献，问题可以转变为我们需要对所有 $l\le i$，求 $\min(i+w-1,r)$，其中 $w$ 是 $\text{LCA}(i,l)$ 的长度

用 dsu on tree 难以维护，注意到 $\text{LCA}$ 也是路径信息，因此可以使用点分治来维护。

分三种情况讨论：

$l,i$ 在分治中心不同的子树，此时 $w$ 为分治中心
$l$ 在分治中心子树外，$i$ 在分治中心内，此时 $w$ 与 $l$ 绑定
$i$ 在分治中心子树外，$l$ 在分治中心内，此时 $w$ 与 $i$ 绑定

每种情况可以变成二维数点或一维数点问题，可以用树状数组解决，复杂度 $O(n\log^2n)$

24. AGC067B - Modifications [K] ✔️

题面

有初始全 $0$ 的序列 $a_1,a_2,\cdots,a_n$，有 $m$ 个区间 $[l_i,r_i]$，你需要选给每个区间选择一个值 $w_i\in[1,C]$，然后选定一个顺序，依次执行区间覆盖操作

求可能生成的 $a$ 种数，对 $998244353$ 取模

$1\le n\le100,1\le m\le\frac12n(n+1)$，保证 $a$ 中所有位置都被至少一个区间覆盖

题解

Sol

先考虑如何判断一个 $a$ 是否合法，正着做不好做，因此我们考虑倒过来：那么我们的操作就是每次选择一个不任意元素都相等的区间，然后将这个区间全标记为任意，如果最后能全变为任意，那么 $a$ 就合法

那么考虑对这个进行 dp，令 $f_{i,j}$ 表示区间 $[i,j]$ 合法的方案数，直接计算不好做，因此我们考虑容斥

如果一个区间不能变为全任意，那么我们找到所有能变为全任意的极大区间，需要保证的就是这些区间无法继续扩展

注意到区间无法继续扩展等价于任意一个询问区间要么全任意，要么只包含一种不任意的数，那么我们令 $g_{l,r,k}$ 表示区间 $[l,r]$ 无法变为任意，并且倒数第二个不同的数（即与 $a_r$ 不同的数）是 $k$

转移即可，复杂度 $O(n^4)$

25. AGC067D - Unique Matching [E] ✔️

题面

给定 $n$，求有多少区间序列 $[l_i,r_i]$ 满足 $1\le l_i\le r_i\le n$，且 $\forall a_i\in[l_i,r_i]$ 的条件能唯一确定一个 $1\sim n$ 的排列 $a$，对给定质数 $p$ 取模

$2\le n\le5000$

题解

Sol

不妨假设最后确定出来是 $p_i=i$，最后乘 $n!$ 即可

如果我们将 $[l_i,r_i]$ 内除了 $i$ 以外的所有点连向 $i$，那么连出来的图应该是 dag，因此我们考虑一些 dag 计数相关

考虑处理出度为 $0$ 的点，即所有没有被区间覆盖的点

设 $f_i$ 表示长为 $i$ 的序列的答案，那么我们枚举最后一个没被覆盖的位置，我们转移需要知道的就是以下两个东西：

长为 $i$，固定 $1$ 不被覆盖，其余随意的方案数 $H(i)$
长为 $i$，固定 $1$ 不被覆盖，其余全被覆盖的方案数 $h_i$

转移式是 $f_j=\sum_{j=1}^iH(j)h_{i-j+1}$

经过一些分析可以得到 $H(i)=f_{i-1}\times i$，那么我们只用考虑如何求 $h_i$

考虑容斥，总方案数是 $H(i)$，依然是枚举最后一个没被覆盖的位置，我们转移需要的是：

长为 $i$，固定 $1$ 和 $i$ 不被覆盖，其余随意的方案数 $G(i)$

转移式 $h_i=H(i)-\sum_{j=2}^iG(j)h_{i-j+1}$

经过同样的分析可以得到 $G(i)=f_{i-2}\times(i-1)^2$

那么直接写出来就是 $O(n^2)$ 的

26. NOI2023 - 合并书本 [K] ✔️

题面

有 $n$ 本书，重量依次是 $w_1,w_2,\cdots,w_n$，磨损值为 $c_i=1$

你每次可以选择两本书 $i,j$，合并得到的新书 $w=w_i+w_j,c=2\max(c_i,c_j)+1$，耗费 $w_i+c_i+c_j$ 的代价

求将所有书合并到一起的最小总代价

$t$ 组数据

$1\le t\le10,1\le n\le100,1\le w_i\le10^9$

题解

Sol

搜索。完全不会啊。

注意到最后会搜出一棵合并树，每个非叶子节点表示合并两本书，并且又右儿子贡献 $w_i$，合并树会有一个自带的磨损值代价 $s$，以及每个叶子会有一个 $w$ 被贡献次数 $c_i$，最后算答案就是把 $a$ 排序和 $w$ 点乘，那么考虑搜索出所有的合并树

如果我们能只关心叶子的 $c_i$ 和整体的 $s$，那么状态数看起来会少一些

考虑从上到下搜索决策树，每次将决策树的一些叶子分裂成两个叶子，但是这样还是无法计算 $s$ 的变化量

于是有人说，考虑最后的合并树，设子树高度为 $h_i$，扫 $d=n,n-1,\cdots,1$，从只有一个根的树开始，每次将所有 $h_i=d$ 的节点全部分裂，这样每次分裂后所有非叶子节点当前的子树高度都会 $+1$，那么 $s\leftarrow 2s+\text{非根非叶子节点数}+\text{本次分裂叶子数}$，可以计算

注意到我们可以直接等效成一次分裂一个子集的叶子，因为我们做的事情是所有非叶子节点子树高度 $+1$，不符合条件的方案权值一定会被算大

注意到这个子集一定是 $c_i$ 的一个前缀，因为在任意子集的前提下，显然这样是更优的。

题解说这样直接写出来可以获得 75pts。

再加一个优化：对一个状态记录 $lim$ 表示转移过来的上一步分裂的叶子数的最小值，由于任意最优操作一定满足分裂的叶子越来越多，那么我们限制一个状态至少分裂 $lim$ 个叶子

加上这个优化后总状态数只有 $<50000$ 多个状态，可以通过（因为每个测试点只用跑一次预处理，对于 $t$ 组数据暴力 check 一遍所有状态即可）

27. UNR8 - 里外一致 [K] ⭐

题面

给定长为 $n$ 的序列 $a_1,a_2,\cdots,a_n$，$q$ 次询问，每次给定一个区间 $[l,r]$，求有多少不同的 $[l,r]$ 内的下标集合 $S$ 使得下标在 $S$ 内的位置的 $a$ 值种数等于下标在 $[l,r]-S$ 内的位置的 $a$ 值种数，对 $2^{64}$ 取模

$1\le n\le3\times10^5,1\le q\le10^5,1\le a_i\le n$

题解

Sol

火大了。

注意到对于一个 $[l,r]$ 内出现次数为 $w$ 的数，其有 $1$ 的方案使 $S$ 内种数减去 $S$ 外种数 $+1$，$1$ 的方案使 $S$ 内种数减去 $S$ 外种数 $-1$，$2^w-2$ 种方案使差不变

也就是 $(x^{-1}+x+2^w-2)$，乘一个 $x$ 变成 $(1+(2^w-2)x+x^2)$，最后求的就是所有乘起来后的 $x^m$ 的系数（$m$ 为 $[l,r]$ 中不同数种数）

注意到模数是 $2^{64}$，因此可以将 $w$ 对 $2^{64}$ 取 $\min$。

现在如果直接枚举取了多少项 $2^w-2$ 只能得到 $64^3$ 的做法，不是很牛。

注意到 $2^w$ 其实非常好，而 $2^w-2$ 就没那么好，因此我们考虑拆出来 $2^w$，也就是把原来拆成 $(x-1)^2+2^wx$，这样我们枚举取了多少个 $2^wx$ 后外面的系数也是好算的

此时外面倒着 dp，$dp_{i,j}$ 表示出现次数 $\ge i$ 的，一共选了 $j$ 项 $2^wx$ 的系数，注意到 $ij\le64$，根据 $\sum(\frac{64}i)^2=O(64^2)$，所以总复杂度是 $O(q\cdot64^2)$ 的

算出每种出现次数有多少数可以使用莫队或扫描线，复杂度 $O(n\sqrt q)$ 或 $O(64\cdot n\log n)$

28. UNR8 - 二维抄袭检测 [E] ✔️

题面

给定一个字符串 $s$ 以及一个 $n\times m$ 的字符矩阵 $t$，$q$ 次询问，每次给定 $i,j,p$，询问：

从 $t_{i,j}$ 开始向下或向右走能走出来的与 $s[p:]$ 匹配的最长路径的长度

$1\le|s|,q\le10^6,1\le n\le10,1\le m\le5\times10^4$

题解

Sol

路径的形态不好考虑，因此我们先考虑一些愚蠢的策略，比如一直向右走，这是两个后缀的 lcp

走不动之后我们需要向下转，设我们走到了 $(x,y^\prime)$，你们在其斜线靠左的部分是否可达都不重要，因为不会对答案造成贡献，那么我们需要知道的就是所有 $(x_1,y_1)$，满足 $x_1>x,x_1+y_1=x+y^\prime$ 是否可达，那么走到这里之后，我们最靠上能访问的行至少向下移动了 $1$，也就是这样的情况只会发生 $O(n)$ 次

那么我们现在需要解决的是，对于一个串 $(x,y)-(x,y^\prime)$，给定 $(x,y)$ 斜线上的可达状态，求 $(x,y^\prime)$ 斜线上的可达状态

这个可以用二进制压位，然后在猫树上维护信息，在猫树上维护中点斜线上每个格子向左向右，能走到斜线上的哪些格子，复杂度 $O(n^2m\log m+qn^2)$

如果使用 SA 求 lcp，总复杂度为 $O(L\log L+n^2m\log m+qn^2)$，但是 SA 是一场宏大的骗局，所以应该使用二分 hash 判断 lcp，复杂度 $O(L+n^2m\log m+qn(n+\log m))$

29. UNR8 - 难度查找 [K] ⭐

题面

交互题。

有一个 $n\times n$ 的正整数矩阵 $a$，满足每行递增且每列递增，你每次可以询问一个位置的值，求第 $k$ 小

$1\le n\le2\times10^5,1\le k\le n^2,0\le a_i\le10^{18}$，最多询问 $10^6$ 次

题解

Sol

啊啊啊。

直接做不好做，考虑提取偶数列，我们在偶数列中求第 $\lfloor(k-n)/2\rfloor$ 大，那么答案一定包含这些值，现在我们有 $\lfloor(k-n)/2\rfloor\times2$ 个数了，需要再添加 $O(n)$ 个，使用 priority_queue，不断添加每一行最右边的数，实现这个事情

偶数行列交替取，目前我们的询问次数是 $T(n,m)=T(m,n/2)+2n$，即 $6n$

加记忆化以及一个剪枝：如果 $(x-1,y)$ 或 $(x,y-1)$ 不在前 $k$ 小里，就不将 $(x,y)$ 加入 priority_queue

可以说明，这样剪完之后询问次数最多为 $5n$

具体地，考虑 $T(n,n)$ 变为 $T(n/2,n/2)$ 的过程，我们说明最多会使用 $2.5n$ 次询问

注意到如果我们每次添加都是行的最后一个元素，那么设在处理完 $T(n/2,n)$ 后，设第 $i$ 行取了 $a_i$ 个，处理完 $T(n,n)$ 后，第 $i$ 行取了 $b_i$ 个，那么在处理 $T(n/2,n)$ 时我们会问 $n/2+|\{a_i\}|$ 次，在处理 $T(n,n)$ 时我们会问 $n+|\{b_i\}|$ 次

不妨先假设操作次数是 $3n/2+n+|\{a_i\}|$，考虑过程中哪些地方会省操作

注意到对于一个 $a_i\neq a_{i-1}$，$(i,a_i+2)$ 一定在 $T(n/2,n)$ 的时候被问过了，此时如果 $a_i\neq b_i$，那么 $(i,a_i+2)$ 不需要被重新问一次，询问次数可以 $-1$，如果 $a_i=b_i$，那么 $b$ 一定不能包含 $a_i+1$，$|\{b_i\}|$ 可以 $-1$

因此最后一定减了 $|\{a_i\}|$，也就是总这部分询问次数最多为 $2.5n$

那么总共询问次数最多为 $5n$

30. UNR8 - 大海的深度 [K] ✔️

题面

给定 $a_1,a_2,\cdots,a_n$，$q$ 次单点修改，每次修改后输出 $\sum_{1\le i\le j\le n}\min(a[i:j])$

$1\le n,m\le2\times10^5,1\le a_i\le10^6$

题解

Sol

asdkchksafdlkajfklasdfljghkjadfdf

考虑单次答案怎么求：有两种方式，分治或者笛卡尔树，而动态维护笛卡尔树是一个很困难的事情，因此我们考虑分治

那么分治用一个 $\log$ 的代价将问题转化为统计跨过中点的所有区间

考虑计算 $\ge j$ 的区间数量，那么最后的答案就是 $\sum_j p_jq_j$，其中 $p_j$ 表示 $[L,M]$ 内最后一个 $\le j$ 的数到 $M$ 的距离，$q_j$ 表示 $[M+1,R]$ 内第一个 $\le j$ 的数到 $M+1$ 的距离

直接做的话，这是一个单点修改，全局求 $\sum\min(p^\prime[1:j])\min(q^\prime[1:j])$，用单侧递归线段树可以做到 $\log^3$

单侧递归无用论.jpg

考虑换一换维度：按照 $j$ 为时间轴，询问为下标，注意到此时每个存在过的数，对 $p$ 和 $q$ 是区间取 $\min$，最后查询的是每个位置 $pq$ 的历史和

这个使用 segbeats 维护，加上外面的 $\log$，复杂度 $O(n\log^2n)$

实现较为复杂。

31. UR25 - 见贤思齐 [E]

题面

有 $n$ 个变量 $x_1,x_2,\cdots,x_n$，给定它们的初值，额外给定数组 $p_1,p_2,\cdots,p_n$，每一时刻，下面的事情会同时发生：

对于所有 $i$，如果 $x_{p_i}\ge x_i$，那么 $x_i\leftarrow x_i+1$

$q$ 次询问，每次询问给定 $g,d$，求 $x_g$ 在 $d$ 时刻的值

$1\le n,q\le2\times10^5,1\le a_i\le10^9,1\le d\le2\times10^5$

题解

Sol

手模。

首先一个环，可以发现最小值一定在不断 $+1$，这个也容易归纳证明

那么我们就可以把环断开，转化成树上的问题

接着手模，我们可以发现当 $x_i$ 和 $x_{p_i}$ 第一次相等之后，$x_i$ 在 $d$ 时刻的值等于 $x_{p_i}$ 在 $d-1$ 时刻的值 $+1$

相当于我们对每个节点求 $tim_i$ 表示 $x_i$ 第一次和 $x_{p_i}$ 相等，那么求答案就是链上查询最后一个 $\ge x$ 的值，这个可以树上倍增，求 $tim$ 的话套一个二分即可

复杂度 $O(n\log^2n)$

32. UR25 - 装配序列 [K] ✨

题面

给定 $1\sim n$ 的排列 $p$，定义 $P$ 为 $p$ 重复无穷多次得到的结果，$m$ 次询问，每次给定一个 $x$，求 $P[1:x]$ 的最长严格递增子序列

$1\le n\le2\times10^5,1\le m\le10^6,1\le x\le10^{18}$

题解

Sol

太抽象了。

考虑贪心求 LIS，但直接做显然没前途，考虑顺着值扫，维护下标序列，即 $f_{i,j}$ 表示考虑完值 $=i$，长度为 $j$ 的子序列最早出现位置，那么每次加值就是二分位置然后覆盖进去，最后的答案就是最后一个 $\le x$ 的数的位置

出于某种原因，每种数保留的位置在任何时候都是一个前缀，不妨假设 $pos=i$ 的数保留了 $c_i$ 个，分析一下加入 $pos=x$ 的数 $i$ 时会产生什么影响

依次考虑它顶掉的下一个数，那么就是顺次执行如下过程：

$c_x\leftarrow 0$
对于每个 $[x+1,n]$，如果 $c_x<c_i$，那么交换 $c_x,c_i$
对于每个 $[1,x-1]$，如果 $c_x<c_i-1$，那么交换 $c_x,c_i$，然后 $c_x\leftarrow c_x-1,c_i\leftarrow c_i+1$
最后 $c_x\leftarrow c_x+1$

直接做是 $O(n^2+m\log n)$ 的

注意到 $\sum c_i=O(n)$，因此我们可以考虑根号分治维护，具体地，对于 $\le B$ 的 $c_i$，我们发现只用考虑它们第一次出现位置（从 $x$ 出发），因为在过程中 $c_x$ 一定单调增，对于 $>B$ 的 $c_i$ 我们直接找到所有位置

这样我们可以在 $O(B\log n+\frac nB)$ 的时间复杂度内找到 $O(B+\frac nB)$ 个可能有用的位置，直接暴力判一下即可

大于 $B$ 的部分需要精细实现才能做到不带 log

33. QOJ8938 - Crawling on a Tree [K] ⭐

题面

给定一棵 $n$ 个点的树，初始 $1$ 号点上有 $m$ 只龟，每条边有两个属性 $l,k$，$l$ 表示这条边的长度，$k$ 表示这条边最多经过的龟数（经过 $k$ 次后不能再经过）

第 $i$ 个点有一个要求 $c_i$，表示必须有 $c_i$ 只不同的龟经过这个点，求这 $m$ 只龟的经过的距离 $\sum l$ 总和的最小值，或判断无解

给定 $M$，请输出 $m=1,2,\cdots,M$ 的所有答案

$2\le n\le10^4,1\le M\le10^4$

题解

Sol

考虑树形 dp，令 $dp_{i,x,y}$ 表示 $i$ 的子树，一共进入了 $x$ 只龟，有 $y$ 只龟不回来了

那么注意到 $x_u,y_u$ 需要满足的若干限制：

$x_u\ge y_u$
$2x_u-y_u\le k_u$，其中 $k_u$ 为 $u$ 父亲边的 $k$ 值
$x_u\ge\max x_v$
$y_u=\sum y_v$

那么可以写出一个 $O(nm^4)$ 的转移，这个十分愚蠢，考虑优化

注意到对于同一个 $y$，一定 $x=\max(y,\max c)$ 的时候取到最小值，其中 $\max c$ 为子树 $c$ 最大值，那么可以简化状态为 $dp_{i,y}$，转移 $O(nm^2)$

进一步可以归纳证明 $dp_i$ 关于 $y$ 是凸的，转移闵和即可，复杂度 $O(nm)$

34. QOJ5095 - 九王唱 [E] ⭐

题面

有 $n$ 个人，$n+1$ 首歌，第 $i$ 个人有一个 $1\sim n+1$ 的排列 $a_i$，表示第 $i$ 个人对第 $j$ 首歌的喜爱程度

有一个整数 $p$，你需要按 $p,p+1,\cdots,n,1,2,\cdots,p-1$ 的顺序考虑所有人，每个人可以删掉任意一首还没有被删除的歌，每个人都希望