admin官方

下面记 ii 位置上初始时有 aia_i 颗星星。

首先，可以证明任何一个状态可以抵达的终止状态（被定义为无法进行任何操作的状态）是一定的，与操作无关：

证明：

考虑存在两个合法序列，分别在 ii 上操作了 uiu_i 和 viv_i 次，因为序列无法继续操作，则 ai−2ui+ui−1+ui+1≤1a_i-2u_i+u_{i-1}+u_{i+1}\leq 1。

因为 uu 和 vv 不同，不妨记录第一次出现某个 viv_i 大于 uiu_i 的位置在 ii（小于的情况显然是对称的），记录此时状态为 ww。由于这是第一次超过，所以邻居满足 wi−1≤ui−1,wi+1≤ui+1w_{i-1}\leq u_{i-1},w_{i+1}\leq u_{i+1}，那么有：ai−2wi+wi−1+wi+1≤ai−2ui+ui−1+ui+1≤1a_i-2w_i+w_{i-1}+w_{i+1}\leq a_i -2u_i+u_{i-1}+u_{i+1}\leq 1。

但是要操作 ii 至少要有两颗星星，矛盾！

故 uu 和 vv 相同。

（注：可能更直观的理解方式是：现在不对 xx 操作未来也要操作，但这不太好书写，上面的内容实际上在形式化表述这件事）

接下来我们考虑求出最终的稳定状态，这可以通过每次尝试分裂区间完成，我们从小到大插入点，不难发现势能是 O(n)\Omicron(n) 的，使用 map 之类的东西就可以快速维护。

求出稳定状态后，可以简单地求出 tit_i 代表 ii 位置上被操作了多少次，记稳定状态是 bb。不妨设 mex⁡\operatorname{mex} 为 mm，则如果要让它更大，我们需要进行若干次 (x−1),(x+1)→x,x(x-1),(x+1)\to x,x 的反向操作。如果想要让 mex⁡\operatorname{mex} 变大 kk，我们需要进行若干次反向操作。经过一些推导，以下条件是必要的：

  1. bb 中存在 −1,m+1,m+2,⋯m+k-1,m+1,m+2,\cdots m+k，否则我们无法完成移动。
  2. 定义 hih_i 为 ii 被 [0,m],[1,m+1],⋯[k−1,k−1+m][0,m],[1,m+1],\cdots [k-1,k-1+m] 中的多少个区间覆盖，则应该有 ti≥hit_i\geq h_i，这是因为我们必须在 ii 位置上完成 hih_i 次撤销。

我们下面证明这个条件是充分的：

我们从 bb 开始依次撤销区间，第 ii 次尝试撤销 [i,i+m][i,i+m]（我们下文将用 cc 来代表当前的状态），我们将会通过一些精细的讨论证明：每个状态都是由初始状态可达的：

我们归纳的证明区间 [i,i+m][i,i+m] 在 撤销前 始终满足如下结构：ci−1≥1,ci,ci+1,⋯ci+m−1=1,ci+m=0,ci+m+1=1c_{i-1}\geq 1,c_{i},c_{i+1},\cdots c_{i+m-1}=1,c_{i+m}=0,c_{i+m+1}=1，并且在 撤销前，存在一种操作序列使得 [i,i+1,⋯ ,i+m]\boldsymbol{[i,i+1,\cdots,i+m]} 是操作序列的后缀。

首先我们证明如果满足上述结构，那么一定存在操作序列使得 [i,i+1,⋯ ,i+m][i,i+1,\cdots,i+m] 是操作序列的后缀：这是因为 i+mi+m 位置一定被操作过。且 i+mi+m 是否操作只会影响 i+m±1i+m\pm 1 能否操作。但是最后 i+mi+m 位置为 00，故 i+mi+m 最后一次操作后一定没有 i+m±1i+m\pm 1 影响它，故我们可以将对 i+mi+m 的操作调整至最后！随后我们撤销 i+mi+m 的操作，此时 i+m−1i+m-1 变为 00！依次向前递推便可以撤销掉这个区间的操作。我们发现操作后 [i+1,i+m][i+1,i+m] 变为 11，i+m+1i+m+1 变为 00。同时因为对 bb 的判定，i+m+2i+m+2 是 11。故符合我们的归纳假设。

因此条件是充分的，证毕。

二分检查上述条件即可，复杂度 O(nlog⁡n)\Omicron(n\log n)。

本题的部分分主要按照 ∑n\sum n 和 aia_i 的范围分层。小范围数据中，点的位置和数量都很小，选手可以直接模拟可达状态，或者用 BFS 枚举演化过程，从而观察 mex 的变化规律。中等范围数据限制 aia_i 不大，允许选手使用数组维护每个位置的点数与可达区间。特殊性质中所有 aia_i 相同，结构非常规整，可以先分析单点堆积向两侧扩散的规律。最终数据中 aia_i 可达 10910^9，要求选手不能依赖位置值域，而要维护若干区间或事件，直接刻画哪些位置最终可能出现。