高爸的杂题练习 3

Cool Slogans

给出一个字符串$S$，要求构造一个字符串序列$s_1,\cdots,s_k$满足：

1. $s_k=S$；
2. $s_{i}$是$s_{i+1}$的子串且在$s_{i+1}$中出现了至少$2$次（出现的位置可以部分重叠）。

求出最大的$k$。

$n\le 2\times 10^5$。

摘要：Fail 树上双指针，线段树维护 Right 集合。

我们可以让$s_k$是$S$的子串，这样答案不会变劣。

容易发现，一定存在一种最优方案使得：

1. $s_k$是$S$的子串；
2. $s_i$是$s_{i+1}$的后缀且在$s_{i+1}$中出现了至少$2$次（出现的位置可以部分重叠）。

这样的话$s_i,s_{i+1}$就是在 Fail 树上的祖先关系。

考虑建出$S$的 Fail 树后，记$f_u$表示$s_k$为$u$代表的子串时的$k$的最大值。我们可以不停跳父亲，直到遇到第一个在$u$中出现 2 次的状态，然后转移。然后容易发现我们可以用树上双指针（或者倍增、二分）来完成这个过程。因此问题转化为，如何快速判断状态$v$在状态$u$中出现了至少 2 次。

这个问题也不难。使用线段树合并求出每个结点的 Right 集合后，我们只需要在$u$的 Right 集合中随便找一个位置，然后在$v$的 Right 集合中求出这个位置的前驱就可以判断了。

时间复杂度$O(n\log_2n)$。

代码

How Many Substrings

给你一个串$S$，$q$次询问$(l,r)$，问$S[l,r]$的本质不同子串的个数。

$|S|,q\le 10^5$。

摘要：离线，线段树按左端点统计子串个数，在 Fail 树链上更新线段树，用 LCT 维护 Fail 树。

考虑离线，将询问按右端点分类。

对于 S 的一个前缀$S[1,x]$，维护序列$c_i$表示最晚出现位置的左端点为$i$的本质不同子串数。因此对于$r=x$的询问，我们可以查询$c$上的区间和来求出答案。

当在$S[1,x]$后面加一个字符，我们就需要更新一部分子串的最晚出现位置。

容易发现，在 S 的 SAM 增量构造过程中，我们插入了$S[x+1]$这个字符后，Fail 树上新的 Last 到根的路径上的状态的最晚出现位置都发生了变化。因此我们可以暴力跳 Fail 树的父亲来更新$c$。由于一个状态$u$代表了长度为$[\text{len}(\text{fail}(u))+1,\text{len}(u)]$的若干个子串，因此一次更新操作相当于是做$O(1)$次区间加（减）。

使用线段树维护$c$，则时间复杂度是$O(n^2\log_2n)$的。

容易发现，对于 Fail 树上的一条链（端点为祖孙关系的链）$P$，如果满足$P$中的所有结点的最晚出现位置相同，那么$P$这条链所代表的所有子串的左端点也是一段连续的区间。因此对于一条链我们可以在$O(\log_2n)$的时间内更新$c$。

既然可以快速维护一条链的信息，那么我们使用 LCT 维护 Fail 树即可，时间复杂度$O(n\log_2^2n)$。

代码

历史研究

给你一个长度为$n$的序列$A$，定义$x$在区间$[L,R]$中的权值为$x$的出现次数乘$x$。定义区间$[L,R]$的权值为$x\in[L,R]$的最大的$x$的权值。

$q$次询问区间权值。

$n,q\le 10^5$。

摘要：分块。

考虑分块，设块大小为$T$。预处理$f(i,j)$表示第$i$块到第$j$块的区间的权值。

预处理$v_x$表示权值$x$的出现位置集合。

查询的时候，整块的部分直接$O(1)$在$f$上查询。零散的部分，我们枚举零碎部分的权值$x$，然后在$v_x$上查询$x$在$[l,r]$中的出现次数来更新答案。

要离散化。

预处理复杂度$O(n\log_2n+\frac{n^2}{T})$。查询复杂度$O(qT\log_2n)$且在线。取$T=\sqrt{n}$可过。

代码

WC2013 糖果公园

给出两个序列$W,V$。定义权值$x$在可重集合$S$中的价值：假设$x$在$S$中出现了$k$次，则价值为$\sum_{i=1}^kV_xW_i$。一个可重集合的价值是其中所有权值（不是所有元素）的价值和。

给你一棵树$T$，定义其中的点的点权为$C_i$。有$q$次操作：

1. 修改单点点权；
2. 询问从$x$到$y$路径上的点的点权组成的可重集合的价值。

$n,q,|W|\le 10^5,C_i\le |W|,n=|V|$。

摘要：树上带修莫队。

考虑一条链且不带修改的情况。容易想到莫队算法。复杂度$O(n\sqrt{n})$。

考虑一条链且带修改的情况。那么加一维时间上去，由于加入一个权值和删除一个权值的复杂度都可以做到$O(1)$，因此复杂度为$O(n^{\frac{5}{3}})$。

考虑原问题。不妨求出任意一个 DFS 序。那么从$x$到$y$的路径可以在 DFS 序列上表示为一个区间。如果一个点在区间中出现了偶数次，那么它就不在这条路径上。那么我们就在 DFS 序列上做莫队即可。

更具体地，对于点$u$，我们记录第一次到达这个点的 DFS 时间戳，以及从这个点回溯时的时间戳，分别为$L_u,R_u$。显然$L_u\le R_u$。那么从$x$到$y$的路径有两种情况：

1. $x$和$y$是祖孙关系（$x=y$的情况也包含在这里）；
2. $x$和$y$不是祖孙关系；

对于第一种情况，设$x$是$y$的祖先，显然$L_x\le L_y$。我们取$[L_x,L_y]$区间做为路径$(x,y)$对应的区间。容易发现，路径上的每个点$u$的$L_u$都在区间中出现了一次，$R_u$则没有出现；

对于第二种情况，设$z=\text{lca}(x,y)$，不妨设$L_x<L_y$，显然$R_x<L_y$。则我们取$[R_x,L_y]$作为路径$(x,y)$对应的区间。容易发现，$x$到$z$路径上每个点$u$的$R_u$都出现了一次；而$y$到$z$路径上的每个点$u$的$L_u$都出现了一次。但$z$是个例外，$L_z,R_z$都没有出现。因此我们在处理这个询问的时候要单独把$C_z$加上去，统计完了再减掉。

在莫队移动端点的过程中，通过判断结点出现次数的奇偶性来决定是加入权值还是删除权值即可。

时间复杂度$O(n^{\frac{5}{3}}+n\log_2n)$。

代码

在线区间众数查询

给出长度为$n$的序列$a$，有$m$次询问，每次查询区间众数的出现次数。强制在线。

$n,m\le 5\times 10^5,a_i\le 10^9$。（2 秒）

摘要：分块。

考虑分块。设块大小为$T$。

预处理$w(l,r)$表示第$l$块到第$r$块的区间众数的出现次数，时间复杂度$O(\frac{n^2}{T})$，空间复杂度$O(\frac{n^2}{T^2})$。

预处理序列$v_{x}$表示数值$x$在$a$中出现的位置。预处理$p_i$表示$a_i$在$v_{a_i}$中出现的位置。时间复杂度$O(n)$。

考虑查询。则区间$[L,R]$的众数出现次数有两种情况：

1. 等于整块的众数；
2. 出现次数大于整块的众数。

整块的众数可以$O(1)$查询。考虑零散部分。假设当前的答案是$C$，考虑判断答案能否为$C+1$。

以左边的零碎部分为例。我们枚举其中的数$a_x$，那么$a_x$就是第$p_x$个出现的$a_x$。我们$O(1)$求出第$p_x+C$个$a_x$出现的位置$P$，如果$P\le R$说明$a_x$在$[L,R]$中出现的位置至少是$C+1$。

右边的类似。

零碎部分的大小是$O(T)$的，因此$C$最多增加$O(T)$次。查询的复杂度是$O(T)$。

因此时间复杂度为$O(\frac{n^2}{T}+n+mT)$。

取$T=\sqrt{n}$。时间复杂度$O((n+m)\sqrt{n})$，空间复杂度$O(n)$。

代码

Souvenirs

给出长度为$n$的序列$a$，有$m$次询问形如$(l,r)$，求$\min_{l\le x<y\le r}|a_x-a_y|$。

$n\le 10^5,m\le 3\times 10^5,a_i\le 10^9$。

离线 扫描线 权值线段树

考虑离线，我们对每次询问$(l,r)$求$\min_{l\le x<y\le r,a_x\ge a_y}(a_x-a_y)$，然后求$\min_{l\le x<y\le r,a_x\le a_y}(a_y-a_x)$，两者取$\min$即可。考虑求前者。

考虑使用扫描线。即我们每次加入$a_i$并处理所有$r=i$的询问。我们维护序列$c$，$c_j$表示在扫描线的当前状态下，$l=j$的询问的答案。

那么当我们加入了$a_i$之后，显然我们会用$a_j-a_i(a_j\ge a_i)$的值来更新某些询问的答案。自然想到，我们想办法找到最大的$j$使得$j<i,a_j\ge a_i$（$a_i$往前第一个比它大的数）。那么$c[1,j]$的值就都要对$a_j-a_i$取$\min$。

第一部分

但是只有这一个$j$是不够的。我们还需要找更多的$j'(j'<i,a_{j'}\ge a_i)$，并用$a_{j'}-a_i$来更新答案（关于如何找这些$j$见第二部分）。

我们还要求$a_{j'}-a_i<a_j-a_i$，即$a_{j'}<a_j$。因为你用$a_{j'}-a_i\ge a_j-a_i$的$j'$再去更新答案是没有任何意义的，你已经有了$a_j$了。

上述有关$j'$的条件可以容易地推出$j'<j$。当然，我们希望$j'$尽可能大。

我们还可以加一个条件：$a_{j'}-a_i<a_j-a_{j'}$。因为区间$[j',i]$是包含$[j',j]$的。如果$a_{j'}-a_i\ge a_j-a_{j'}$也没有更新意义。这是本题的一个关键点。有了这个条件我们可以推出$a_{j'}<\frac{1}{2}(a_i+a_j)$（这个条件比$a_{j'}<a_j$更强）。

综上所述，当我们用$a_j-a_i$更新完$c[1,j]$的值后，我们尝试找到下一个$j'$，并用$a_{j'}-a_i$更新$c[1,j']$的值。则$j'$需要满足条件：$j' <j,\,a_i\le a_{j'} <\frac{1}{2}(a_i+a_j)$。

当我们用$a_{j'}-a_i$更新完后，我们可以再如法炮制找到下一个$j''$，可以类似地发现$j''$满足$j'' <j',\,a_i\le a_{j''} <\frac{1}{2}(a_i+a_{j'})<\frac{3}{4}a_i+\frac{1}{4}a_j$。

以此类推，则$j^{(k)}$需要满足的条件是

$$j^{(k)} <j^{(k-1)},\,a_i\le a_{j^{(k)}} <\frac{1}{2}(a_i+a_{j^{(k-1)}})<\frac{2^k-1}{2^k}a_i+\frac{1}{2^k}a_j =a_i+\frac{1}{2^k}(a_j-a_i)$$

因此我们得到$a_i\le a_{j^{(k)}}<a_i+\frac{1}{2^k}(a_j-a_i)$，因此$k\le O(\log_2W)$，即我们最多找到$\log_2W$个有更新价值$j$来更新。

如果使用线段树维护$c$的话，那么做一次更新的复杂度是$O(\log_2n)$的，更新$a_i$的复杂度就是$O(\log_2n\log_2W)$的。

第二部分

那么接下来的问题是：

1. 如何找到最大的$j$使得$j<i,a_j\ge a_i$。
2. 找到最大的$j^{(k)}$使得$j^{(k)} <j^{(k-1)},\,a_i\le a_{j^{(k)}} <\frac{1}{2}(a_i+a_{j^{(k-1)}})$（记$j^{(0)}=j$）。

一个直接的思路是对$a[1,i-1]$建立权值线段树，在对应的权值上存下标。那么上面两个问题就相当于是求区间$\max$。当然也可以建立离散化的权值线段树。

那么这部分的查询复杂度就是$O(\log_2n\log_2W)$。

总复杂度$O(n\log_2n\log_2W)$。

小插曲：在求$a_j\le a_i$的情况的时候，可以直接把$a_i$变成相反数再做一次。

代码