数据结构专题 #1

A Strange Addition

水题。

考虑 $dp[i]$ 表示当前考虑到第 $i$ 位，有多少种有序对 $(a,b)$ 在前 $i$ 位满足条件。

转移考虑每次往 $(a,b)$ 后面分别添加一位，然后考虑得到的数，要么得到的数会添加两位，要么只添加一位。所以转移就是

dp[i] = dp[i-1]S[A_i] + dp[i - 2] S[A_i+10A_{i-1}]

其中 $S[i]$ 表示有多少种两个一位数加起来是 $i$ 。

这个转移显然可以写成矩阵乘法的形式，每个位置维护一个矩阵

\begin{bmatrix} S[A_i] & S[A_i + 10A_{i-1}] \\ 1 & 0 \end{bmatrix}

每次修改就修改这个位置本身和下一个位置的矩阵，把矩阵放到线段树上即可。

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

WA 了一次，因为没有判当 $A_i + 10A_{i-1} > 20$ 的时候，而 $S$ 只预处理到了 $20$ 。

B Geometers Anonymous Club

~~毒瘤萃老师开始告诉我求闵可夫斯基和的面积~~

考虑求闵可夫斯基和的过程，极角排序后从小到大依次拿向量即可。所以可以发现，实际上顶点的个数就是不同的斜率个数，因为多边形的边数等于点数。

所以我们只需要算区间内的本质不同斜率个数。这个是经典操作，可以记录上一次出现的位置 $lst[i]$ 看看是否小于区间左端点即可。

现在要数的就是 $l \le i \le r , lst[i] \le l - 1$ 的个数。扫描线一下，按照 $lst[i]$ 从小到大加入即可，加入后算一下区间和即可。

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

WA 了一次，因为数组没开够 $3 \times 10^5$ 。

C Max Mex

好题。以前打 vp 的时候做到过。

直接粘我补 vp 的时候的题解：

这个题做法还算简单，由于是个排列，考虑在值域上开一个线段树，维护如果想要同时包含区间内的值的最小路径，或维护不存在这样的路径。这个东西的合并就是一个路径求并的过程，而且如果合并后不是路径直接判掉即可。查询就是线段树上二分，修改就直接单点改。

路径求并，直接在这四个点中枚举两个点，看看剩下的点是不是都在这条路径上，通过 dfs 序和深度就可以判。

如果像我一样信仰一波直接倍增 LCA 然后就 T 飞了。倍增求 LCA 的话这东西复杂度 $O(n\log^2 n)$ ，试了试由于 pushup 常数不小跑不过去。

然后改成 ST 表就过了。复习一下，ST 表求 LCA 的方法是记一个进入一个点记录一次的欧拉序，回溯到这个点也算数，然后找 $u,v$ 在序列中第一次出现的位置之间的最浅点即可。

复杂度 $O(n\log n)$ 。带差不多 $4\times 3 \times 2$ 的常数。

两次罚时，第一次是倍增数组求错，第二次是不能带 LCA 的 $\log$ 被卡 T 了。

D Indie Album

去年八月刚学 ACAM 和 SAM 的时候做过，感觉那时候写的题解不太好，再写一下。。

其实给串的方式是直接给出一个 Trie 。也就是说询问其实就是问某个串在 Trie 上某个点到根的路径形成的串中的出现次数。

可以先把 ACAM 的 fail 树给建出来，那么当我们到达一个节点 $u$ 的时候，询问就是问这个点在 Trie 中到根路径上有多少个点出现在这个点 fail 树的子树内。

那么就有了一个离线做法，我们 dfs 整棵树，到达一个点就把它在 fail 树上的 dfs 序的位置增加 $1$ ，询问就是问子树和，也就是区间和。单点加区间和可以用 BIT 搞定。

复杂度大概是 $O(n\log n)$ 。

当时 1A 的。这东西写着很爽。

F Prince's Problem

这个乘法由于是模意义下的，是有逆元的，因此可以把一个询问拆成四个询问，分别求 $u,v$ 到根路径上这个东西的乘积，以及 $\text{LCA,fa[LCA]}$ 到根路径上这个东西的乘积，然后离线下来。

现在考虑进行一个 dfs ，考虑一个点到根路径上的这个东西怎么维护。

我们先对所有数进行分解质因子，可以通过记录最小质因子来做到 $O(\log v)$ 分解。

然后 dfs 到的每一个点，我们考虑记一个 $F[w]$ ，当 $w = p^k$ 时，值为 $\prod \gcd(a_i , p^k)$ 。考虑加入一个数如何维护这个东西，假设这个数在这个质因子上是 $p^t$ ，那么对于 $i \le t$ ，对 $F[p^i]$ 的贡献就是 $p^i$ ，否则就是 $p^t$ 。

这个贡献乘进去的复杂度是 $O(\log v)$ ，质因子的个数是 $O(\omega(v))$ 大约是 $8$ 。

所以总复杂度是 $O(n\log v \omega(v))$ 。常数有 $8$ 左右，但是还是能跑进 $\text{1s}$ ，因为其实 $\log v$ 很不满。

也是一个写着很爽的题。

H Extending Set of Points

看到这个题比较容易想到的想法是，对横坐标和纵坐标分别建点，然后对于每个点 $(x,y)$ 我们考虑连 $x \to y$ 这么一条边。不难发现怎么连这都是个二分图。

然后考虑二分图的任何一个连通块。画一下可以猜一个结论，对于任何一个二分图的连通块，一定可以通过扩展操作变成两边所有点之间都有连边。

怎么证明呢？考虑把两个已经满足两边所有点间都有连边的二分图通过一条边合并起来。

如图，考虑加入一个绿边，可以把图中蓝色的边全部连上，再把黄色边全部连上。

这样就可以归纳证明任何时刻都可以调整成满的二分图。

所以答案就是当前所有二分图连通块的两边点数的乘积。

于是可以线段树分治转只插入和撤销，用可撤销并查集维护当前连通块大小以及每个连通块某一边的大小即可。

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

J Fibonotci

思路很简单但是实现不优秀就很容易自闭的题。比如我写得非常丑，写了 4.4k 还挂了好几次才过，优秀一些的实现只需要 1.5k 。

我的实现方法大概是用线段树维护 $s_0 \dots s_{n-1}$ 对应的矩阵。然后倒着处理所有特殊位置，两个特殊位置之间的整块用矩阵快速幂加速，有特殊位置的块在线段树上修改。看起来是一个非常简单的做法，实际上如果细想会发现一些细节问题：

修改一个位置会对应修改的是 $s_i,s_{(i+1)\bmod k}$ 。也就是说如果修改序列的末尾，会导致下一个块也被改了，这种情况需要在每个块特判开头的上一个位置是否被修改。同样需要特判修改最后一个位置的时候不会继续修改开头。
如果 $k$ 所在的就是开头块，那么要特判掉 $0$ 的位置。同样对于任何开头块都要从 $1$ 开始乘。
特判 $k=0,k=1,P=1$ 的情况。
记得各种地方开 long long 。

上面就是我 WA 四次分别的原因，程序中还有很多上取整，下取整需要判整对，总之就是细节非常多。（倒也不愧是这场 Bubble Cup 过的人最少的题）

后来参考了很多代码，还是觉得这份是写得最好的。这份代码直接用 ST 表来维护区间之内的矩乘。不难发现这个题中修改数的操作可以看成互相独立的，这个块修改了下个块又回去，没有必要使用线段树，直接用 ST 表整成一些不同的区间的乘积即可。然后拿一个 map 去维护所有修改点以及修改点修改成了什么，同时把修改点以及修改点的后一个都丢进一个 set 里面，表示这里面的点都需要单独处理。

然后这份代码实现了一个函数

ll s(ll i) {
	if(_mp.count(i))
		return _mp[i];
	return _s[(i + n) % n];
}

就是真正求出一个位置实际上的值是什么。通过这个可以避免很多的特判，包括当前点是否是修改点之类的。

然后就是从头往后扫，考虑如果当前点存在于 set 中，则删去它并把这里乘上，否则把这个位置到 set 中下一个位置之前的一个位置这个区间一起处理，处理方法是 ST 表求前后缀以及中间用矩阵快速幂。

这样做思路清晰，没有特判，可以说是比我实现好很多倍的实现了。关键点在于修改互相其实独立，可以从前向后扫过去。

考虑离线操作，然后从 $1$ 扫到 $n$ ，当我们扫到一个点 $u$ ，我们把所有 $l=u$ 的操作进行了，具体来说就是把 $[l,r]$ 这段区间“反向”，即原本如果是当前点正向连过去现在就变成反着的。同时把所有 $r+1 = u$ 的也进行一次，也就是把这个区间再反回来。然后当 $u \to u+1$ 的时候，把 $u$ 这个点本身给反向。考虑当我们到达一个点 $u$ 的时候我们翻了哪些点。首先这个点之前的所有点在离开的时候都会反向一次，所有如果不考虑区间，现在序列大概长成 $00\dots 00111\dots 1$ 中间的分界点就是 $u$ 。然后考虑所有 $l \le u \le r$ 的区间，我们都给区间进行了反向，因为这个点连向这个区间的所有边都在这样的操作中反了过来。

于是就是统计序列中的 $1$ 的个数。这些都是可以直接上线段树维护的。复杂度 $O(n\log n)$ 。非常好写。

L Two Permutations

好题。

首先，子串是非常简单的。给两个序列分别差分，然后就变成了一个 KMP 的问题。

但是子序列怎么办呢？注意到两个序列都是排列，也就是说 $a_1+x,a_2+x,\dots ,a_n+x$ 这个序列本身的值域是连续的，是 $[x+1,x+n]$ 。这就让我们注意到值域上来。也就是说可以设 $pos[x]$ 表示 $x$ 在 $b$ 中出现的位置。也就是说我们需要找到有多少 $x$ 满足 $pos[x+a_1] < pos[x+a_2] < \cdots < pos[x+a_n]$ 。也就是在 $pos$ 中找有多少长度为 $n$ 的区间使得区间的顺序是 $a$ 的顺序。

a这个问题可以用 Hash 来解决。具体来说，我们可以设 Hash 值是 $\sum a_i B^i$ 。那么在 $b$ 序列中，区间的 Hash 值即是 $\sum i B^{rnk_i}$ 这个东西。如果这两个相同，说明这个区间最小的在 $a_1$ 位，次小在 $a_2$ 位 $\dots$ ，也就是满足了上面说的那个条件。

怎么维护这个东西？这个东西看起来就很具有可合并性，所以可以直接把所有在当前区间的 $pos$ 给激活，也就是让 $pos[r] = i$ 的 $i$ 这个位置放上一个 $r$ ，同时合并的时候就是给右子树的 Hash 乘上左子树的 $siz$ 即可。

复杂度 $O(m\log m)$ 。写着很爽。

N Power Tree

是一个看起来吓人，实际上想一想发现很可做的题。

既然不强在，那么肯定先离线下来把整棵树的形态建好。

考虑当前有一棵树，怎么求一个点对根的贡献？会发现，这个贡献就是 $A[u]$ 乘上路径上的所有点的度数的积。

所以我们可以维护一个线段树，每个位置表示这个位置在当前的树上到根的度数的积，但是只有这个点当前是被加入的才把它的贡献进行 pushup 。每次操作就是加入一个点，并且给一段区间（加入点父亲子树的区间）乘上 $\frac{deg+1}{deg}$ 。

询问的根如果不是 $1$ 不难发现很容易可以差分成每个点到 $1$ 除掉这个点到根路径上的度数的积。

然后就做完了，复杂度 $O(q\log n)$ 。

P Duff as a Queen

有意思的题。

区间进行异或好像不是很好维护，实际上也确实，直接给区间的线性基异或一个数肯定是不对的，这个非常容易举出反例。

由于异或的性质，可以考虑通过差分把区间改变成单点改，对整个序列进行异或差分。我们可以在差分后的序列中询问 $[l+1,r]$ 的线性基，然后把真正的 $A[l]$ 插入这个线性基里面，得到的东西和原本得到的线性基显然是一样的。

然后就做完了，直接拿线段树维护区间的线性基即可，合并就是暴力合并线性基。

主要就是注意到差分后可以通过插入一个数来使得在线性基中原本信息不丢失。

非常好写。复杂度 $O(q\log n \log^2 v)$ 。毕竟 7s ，随便跑过。

R Function

这题是可以在线的。后来发现很多人都写得好写的离线做法。但是其实这题在线做法也挺爽的。

仔细观察一下 $f$ 的定义，就是要选 $i$ 个数，使得相邻两个数的位置的差要么是 $0$ 要么是 $+1$ 。

然后可以发现，贪心一下的话最优的策略肯定是选择很多次 $A_k$ 然后从 $A_k$ 走 $i-k$ 次走到 $A_i$ 。

画一下式子可以发现，就是

f(i,j) = \min_{k \in[j-i+1,i]} \{A_k(i-j+k) + S_j - S_k \}

可以发现是一个斜率优化的形式，就是在区间的凸包上二分斜率。

于是可以用线段树套单调栈来维护凸包，然后就是在区间的几个凸包上进行二分，取最小值即可。

这可能是我第一次写维护直线的斜率优化，感觉比维护点的写着更爽，不过还是需要注意斜率相同的时候的判，应当把所有中间点都弹掉，它们不可能作为最优答案。

S Isolation

很友善的分块题。

考虑 $dp[i]$ 表示 $[1,i]$ 的划分方案。也就是要求之前有多少位置满足 $[j,i]$ 的恰好出现一次的数正好 $1$ 个。不难发现，我们可以到 $i$ 给 $[las[i]+1,i]$ 加上 $1$ ，同时给 $[las[las[i]]+1,las[i]]$ 减少 $1$ 。

然后就成了区间加减，全局小于等于 $k$ 的位置的权值和。可以直接分块维护，块内我们按照权值排序好，每次询问就 upper_bound 即可。每次操作重构一下边缘块，中间打标记。

很好写，复杂度 $O(n\sqrt n \log n)$ 大概也可以看成 $\log$ 在根号里面。