Banknote Collection 命题报告

本来是没有打算写命题报告的。不过在讨论的过程中发现，这题似乎的确有一定的难度。于是就有了本文。

题目大意

题目链接

给出一个长度为$n$的正整数序列$a$。我们可以折叠序列$a$。例如$[3,4,4,3,2,2,3,4,1,3,1,1]$可以折叠为

   3-4╮
╭2-3-4╯
╰2-3-4-1-3-1╮
           1╯

它可以被折叠$3$次。再举一个例子，$[1,1,1,1,1,1]$可以被折叠$5$次：

 1╮
╭1╯
╰1╮
╭1╯
╰1╮
 1╯

形式化地，我们定义$a$的一个折叠序列是长度为$n$的整数序列$b$满足：

1. $b$仅由$1$和$-1$构成，且$b_1=1$；
2. 设$p(i)=[b_i=1]+\sum_{j=1}^{i-1}b_j$。则对于任意$1\le i<j\le n$且$p(i)=p(j)$，必满足$a_i=a_j$。

显然，可能有多个不同的$b$都满足$a$的折叠序列条件。

定义折叠序列$b$的折叠次数为$f(b)=\sum_{i=1}^{n-1}[b_i\ne b_{i+1}]$。那么$a$的最大折叠次数定义为所有合法的折叠序列$b$中$f(b)$的最大值。

现在 Boboniu 正操纵着一个序列$a$。初始时$a$长度为$0$。他会执行$n$次操作，每次他会在$a$末尾加入一个元素。他想知道每次插入元素后，$a$的最大折叠次数。

$1\le n\le 10^5,1\le a_i\le n$。

从左到右

在讨论算法的过程中，我们把序列理解为一个字符集较大的字符串。这样解释起来方便一些。

另外，本文中所有的回文，一般情况都指偶回文。

在开始讨论关于此题的算法之前，我想讲述关于折叠操作的一些直观理解。大家可以想象，你拿着一张纸条做各种各样的折叠。比如对折再对折：

但是其实这种折叠方式（在本题中），等价于你做一个 Z 字型（或者说 M 字型）的折叠：

因为在本题中的折叠次数，实际上指的是折痕的数量。而两种折叠方式的折痕数量是一样的。

考虑一个更具体的例子：$a=[1,2,2,2,2,1,1,2,2]$。我们分别按照以下两种方式折叠：

（红色表示折叠的位置）

实际上，两种折叠方式折出来是等价的。你把第二种折叠方式的外面那个圈收到里面来，就变成了第一种折叠方式：

观察第一种折叠方式，它始终呈 Z 型折叠，并且它是按照从左到右的顺序依次折过来的。也就是说我们得到了两个关键信息：

Key point 1：任意一种折叠方案，都可以通过改变圈的位置，变成 Z 型折叠。

Key point 2：任意一种折叠方案，只要折到了不能继续折下去的程度，那么得到的折痕数量是始终相等的。

也就是说我们把原本的任意折叠，归约成了从左到右依次折叠。

从左到右依次折叠还有一个好处：每次都只折了一层纸。如果随意折叠，就可能会出现折多层纸的情况，这时的折叠次数就要多次计算。比如在上述例子中，第二种折叠方式的第二次折叠就一次折了 3 层纸，因此折痕数量加 3。也就是说，如果我们从左到右折叠，那么只用考虑折叠的次数，不用考虑每次折叠的层数。

这部分希望大家自己动手折叠一下，先理解直观的感受。

接下来，我们就按照从左到右的顺序讨论关于本题的算法。

三折

考虑$[\cdots,1,2,2,2,3,\dots]$中的三个$2$。我们一定会把他们折成一个$2$（$2$次折叠，Z 型）。假设你不折，那么最终的方案里一定含有$[2,2,2]$的子串。于是你就可以再折$2$次来获得更多折痕。

推广之，考虑三个连续的字符串$XYX$，其中$Y$是$X$的反串。那么我们可以贪心地把它们折成一个$X$：

我们称形如$XYX$（其中$Y$是$X$的反串）的字符串为三折。

另外，我们定义最简三折为一个形如$XYX$的字符串，满足它不存在三折真子串。

根据 Key point 2，我们有一个大致的思路：先把所有能折的三折给折了，剩下一个没有三折的串，再来折这个串。具体地，我们分为两个部分：

1. 考虑字符串$b$，初始时为空串。我们执行$n$次操作，每次在$b$末尾插入$a_i$，然后检查$b$是否产生了新的三折，有就折，没有就不折。
2. 对于一个没有三折的串$b$，我们要求出它还能被折多少次。

那么我们只需要在每次做第一步后做第二步，就可以求出每次操作完之后的答案了。

Easy Version

第一部分

设$b$末位插入$a_i$后变成了$b'$。

首先我们证明一个引理，这在之后的复杂度证明中都会发挥作用。

Lemma 1：对于一个串$S$的两个偶回文子串$S[l_1,r_1]$，$S[l_2,r_2]$，如果$[l_1,r_1]$包含$S[l_2,r_2]$的中心且$[l_2,r_2]$包含$S[l_1,r_1]$的中心，那么$S$一定包含三折子串。

证明

不妨设$l_1<l_2$，$|r_1-l_1|\ge |r_2-l_2|$。那么通过简单的构造可以发现：

这样就产生了三折。证毕。

Key point 3：$b'$至多有一个三折。

证明

证明：考虑反证法。

首先，$b'$的三折一定是它的后缀，因为$b$没有三折。

那么如果$b'$产生了多个三折后缀，有三种情况：

黑和红：这种情况很容易反证。在第一个$X$里也会出现一个三折，那么$b$中就含有三折了，矛盾。

黑和蓝、黑和绿：可以发现，蓝色的$XY$和黑色的$YX$形成了 Lemma 1 的情况，绿色的$XY$和黑色的$XY$也形成了 Lemma 1 的情况。因此$b$中含有三折，矛盾。

证毕。

由 Key point 3 我们还可以发现，这个三折一定是最简三折。

因此我们使用一些算法找到这个三折后，把它折叠。折叠的过程就是删掉$b'$的一个偶回文后缀。如果找不到三折，就不变。

第二部分

对于一个没有三折的串$b$，我们要求出它还能被折多少次。

没有三折，我们就只能对折——也就是把一个偶回文前缀或者偶回文后缀折叠。

考虑贪心，以偶回文后缀为例，我们每次折叠最短的偶回文后缀。那么每次折叠的后缀长度一定是严格递增的：

因为如果不递增，那么就会出现 Lemma 1 的情况，导致出现三折，矛盾。

因此$b$折叠出来的应该大致是这个样子：

Key point 4：对于没有三折的串$b$，最多被折叠$O(\sqrt{b})$次。

• 对于偶回文后缀的折叠 ：设$p_i$表示$b[1,i]$的最短偶回文后缀。
• 对于偶回文前缀的折叠：设$q_i$表示，在$b[1,i]$串上从开头开始折叠，每次折叠最短偶回文前缀，最多能折叠到什么位置。设$c_i$表示前缀的折叠次数。

算法描述

我们使用 hash 来处理两个部分。

找三折：对于每个后缀判断是否是偶回文后缀，如果是，就判断是否构成三折。时间复杂度$O(n)$的。

当$b$变成$b'$时：

• 如果没有出现三折，那么我们就$O(n)$求出$p_{|b'|}$，然后$O(1)$地求出$q_{|b'|},c_{|b'|}$（基于$q_{|b|},c_{|b|}$）。然后我们可以$O(1)$更新字符串的 hash。
• 否则我们要删除$b'$的后缀，那么我们直接舍弃那部分的后缀对应的$p,q,c$和 hash 值即可，时间复杂度$O(1)$。

回答询问：我们可以$O(1)$查询$c_i$，$O(\sqrt{n})$查询$p_i$来回答询问。

总时间复杂度$O(n^2)$。

Hard Version

为了让获得更快的算法，我们需要挖掘更多有关三折的性质。

第一部分

我们需要优化找三折的复杂度。

Key point 5：最简三折只有一个偶回文后缀（就是$XYX$的$YX$）。

这个同样可以反证，并结合 Lemma 1 导出矛盾。

根据 Key point 3，我们发现，$b'$的三折一定由它的最短偶回文后缀产生。因此我们只需要快速找到$b'$的最短偶回文后缀，然后看它是否构成三折即可。

Key point 6：$b'$的偶回文后缀数量是$O(\log_2n)$的。

因为$b'$的偶回文后缀不能出现 引理 1 的情况，所以必须是一个包含另一个，且不跨过中心。那么偶回文后缀的长度每次至少倍增：

设$v_i$表示$b[1,i]$的偶回文后缀的集合。由于$v_i$的大小是$O(\log_2n)$的，因此可以使用 vector 维护。于是

• 找最短回文后缀的复杂度就是$O(\log_2n)$的。
• 判断一个串是否是三折，可以转化为判断一个子串是否是回文串，同样可以$O(\log_2n)$判断。
• 在$b$末尾插入$a_i$的时候，可以枚举$v_{|b|}$的偶回文后缀，求出$v_{|b'|}$，时间复杂度$O(\log_2n)$。

如果找到了一个三折，就删掉$b'$的一个偶回文后缀。

这样，找三折以及更新$b$的复杂度就优化为了$O(n\log_2n)$。

第二部分

沿用 easy version 的算法，单次询问的复杂度仍是$O(\sqrt{n})$，可以通过本题。

算法描述

找三折：在$v_i$中查询最小值，时间复杂度$O(\log_2n)$。

当$b$变成$b'$时：

• 如果没有出现三折，那么我们就$O(\log_2n)$求出$p_{|b'|}$，然后$O(1)$地求出$q_{|b'|},c_{|b'|}$（基于$q_{|b|},c_{|b|}$）。然后我们可以$O(\log_2n)$利用$v_{|b|}$求出$v_{|b'|}$。
• 否则，我们要删除$b'$的后缀，直接舍弃对应变量即可。时间复杂度$O(1)$。

回答询问：我们可以$O(1)$查询$c_i$，$O(\sqrt{n})$查询$p_i$来回答询问。

总时间复杂度$O(n(\log_2n+\sqrt{n}))$。

数据

首先肯定有随机数据，然后还要有一些 corner 的情况，还有$O(n\sqrt{n})$的没有三折数据。

验题的时候，丁神在比赛开始前一晚，写了一个暴搜剪枝过了。当时把我吓傻了，然后就赶紧研究了一下，hack 掉了这个暴搜。生成器长这样：

cur = 3
a = [1,1]

for i in range(3,17):
    b = a.copy()
    a.append(cur) # new fuck
    cur += 1
    a.reverse()
    a.extend(b) # link
    a.append(cur) # fuck
    a.reverse()

print(len(a))
a.reverse()
for x in a:
    print('{} '.format(x),end='')