NOI 2025 Day2 C. 绝对防御

Statement

有一个长为 $n$ 的 $0,1$ 序列 $a$，$q$ 次单点翻转，查询这 $q+1$ 个状态中每一个 $a$ 上最小的一个 $k$ 使得「你开始拥有 $a_1,a_2,\cdots,a_k$，然后指针 $p=k$，存在方案持续这个过程直到 $p\geq n$：取 $a_{p+1},a_{p+2}$（如果 $p=n-1$ 的话就只取 $a_{n}$），然后从你已有的数中删除一个 $0$ 和一个 $1$，或者删除两个 $0$（相邻两次删除两个 $0$ 的操作间隔不能小于 $z$），然后将 $p$ 增加 $2$。」

$1\leq n,q\leq 2\times 10^5,\,z=3$

TL: 4s

Solution

不难发现发现合法的 $k$ 是一段后缀，因此先考虑如下问题：在前 $i$ 轮获得了 $A_i$ 个 $0$ 与 $B_i$ 个 $1$。

为了方便接下来动态维护，我们期待得到几个代数式的判定。

设你在第 $i$ 轮是否是删除了两个 $0$ 的状态是 $c_i$，$\{c_i\}$ 的前缀和是 $\{C_i\}$。

那么你的限制是： $$ \begin{aligned} \forall 1\leq i\leq n,\;&C_{i-1}\leq C_i\\ \forall 0\leq i\leq j\leq i+z\leq n,\;&C_i+1\geq C_j\\ \forall 0\leq i\leq n,\;&A_i-i-C_i\geq0\\ \forall 0\leq i\leq n,\;&B_i-i+C_i\geq0 \end{aligned} $$ 于是考虑差分约束，把后两个式子中的 $C_i$ 替换为 $C_i-C_0$ 就好了，判断是否有解就是检查是否无负环。具体来说我们写成标准型是： $$ \begin{aligned} \forall 1\leq i\leq n,\;&C_{i-1}-C_i\leq0\\ \forall 0\leq i\leq j\leq i+z\leq n,\;&C_j-C_i\leq 1\\ \forall 0\leq i\leq n,\;&C_i-C_0\leq A_i-i\\ \forall 0\leq i\leq n,\;&C_0-C_i\leq B_i-i \end{aligned} $$

这张图上的负权边只有可能由后两种边提供，都一定经过 $0$，而只经过前两种边的话从 $x$ 走到 $y$ 的距离是 $\max\{0,\lceil\frac{y-x}{z}\rceil\}$。

因此我们只需要保证 $$ \begin{aligned} \forall 0\leq i\leq n,\;&A_i-i\geq 0\\ \forall 0\leq i\leq n,\;&\lceil\frac{i}{z}\rceil+B_i-i\geq0\\ \forall 0\leq l\leq r\leq n,\;&A_l-l+\lceil\frac{r-l}{z}\rceil+B_r-r\geq 0\\ \forall 0\leq l\leq r\leq n,\;&A_r-r+B_l-l\geq0 \end{aligned} $$ 这里每个式子至多出现一个向上取整，因此可以通过把 $\geq 0$ 改成 $>-1$ 来消掉，然后再两边同时乘 $z$，变为： $$ \begin{aligned} \forall 0\leq i\leq n,\;&A_i-i\geq 0\\ \forall 0\leq i\leq n,\;&i+zB_i-zi+z-1\geq0\\ \forall 0\leq l\leq r\leq n,\;&zA_l-(z+1)l+zB_r-(z-1)r+z-1\geq0\\ \forall 0\leq l\leq r\leq n,\;&A_r-r+B_l-l\geq0 \end{aligned} $$ 对 $A,B$ 做区间加也都是可以通过线段树容易维护出最小值的，而且你注意到对于同奇偶的 $k$ 来说 $x+A,y+B$ 的变化只是平移，因此你可以直接线段树上二分来解决，时间复杂度 $\mathcal{O}(n+q\log n)$。