第十分块 | 感谢毒瘤没在大年初一卡我常。

· · 题解

P6578 [Ynoi2019] 魔法少女网站

  • 雨谷小雨给你一个长为 n 的序列 a，定义区间 [l,r] 的子区间为所有形如 [l',r'] 的区间，满足 l',r' 为整数，且 l \le l' \le r' \le r。
  • 有 m 次操作：
    • 1 x y：将 x 位置的值修改为 y。
    • 2 l r x：查询区间 [l,r] 中有多少子区间的最大值小于或等于 x。

默认 n,m 以及值域同阶。

对于询问，将区间内所有 \le x 的位置看作 1，剩下的看作 0，则答案为全 1 子区间数量。进一步地，一个长度为 z 的极长全 1 连续段对答案的贡献为 \dfrac{z(z+1)}{2}。记 01 序列为 b。

定义一种信息 (l,r,t,s) 分别表示一个区间的极长前缀 1 段长度、极长后缀 1 段长度、区间长度、区间答案，则容易 \mathcal{O}(1) 合并相邻两个区间的信息。

考虑以 B=\mathcal{O}(\sqrt n) 为块长分块。离线逐块处理。维护每个询问合并到当前块时的答案。

先不考虑修改。

散块查询直接和 \mathcal{O}(\sqrt n) 个单点信息合并即可。对于一个整块 [L,R]，记 c_x 表示块内 \le x 的元素个数即 c_x=\sum\limits_{i=L}^R[a_i\le x]，则块内元素 a_i\le x 等价于 c_{a_i}\le c_x。那么一次整块询问可以看成对于 (c_{a_L},\dots,c_{a_R}) 这个序列询问最大值 \le c_x 的子区间个数。

注意到 c_x 为 \mathcal{O}(\sqrt{n}) 级别。考虑把询问挂在 c_x 上，对 c_x 正序扫描线，维护 b 中 0 的位置集合 S 和当前 b 序列对应的信息 \text{cur}=(l,r,t,s)，则相邻两个 0 位置之间就是一个极长全 1 连续段，初始 \text{cur}=(0,0,R-L+1,0)。则从 p-1 扫到 p 时，会删除 S 中所有 c_{a_i}=p 的位置 i。删除一个位置 i 时，记她在 S 中的前驱后继为 \text{pr},\text{nx}。则相当于删除 (\text{pr},i) 和 (i,\text{nx}) 两个极长全 1 连续段再加入 (\text{pr},\text{nx}) 这个极长全 1 连续段。可以减去原来的贡献再加入新的贡献求得新的 s。也可以直接考虑对 s 新增的贡献为包含 i 的全 1 子区间个数，乘法原理得到增量为 (i-\text{pr})(\text{nx}-i)。容易用链表维护 S，删除和找前驱后继都是 \mathcal{O}(1) 的。

对于 l,r，需要支持查询 b 中最左 / 右 0 位置。考虑链表维护 [L-1,R+1] 这个区间，并强制令 b_{L-1}=b_{R+1}=0，那么就是查询端点的前驱 / 后继。

那么对于子区间最大值 \le p 的询问，将所有挂在 p 上的询问与 \text{cur} 合并即可。

接下来带上修改。对于第 i 个块，记修改其内部元素的时刻依次为 (T_1,\dots,T_{k_i})，对于相邻两个时刻之间的询问，块内信息不变，直接做上面这个扫描线即可。注意这样会漏掉 T_{k_i} 至 m 时刻的询问，要在最后补上一次扫描线。一次修改仅会影响 c 数组，可以看成是一次后缀 -1 和一次后缀 +1。对于所有块有 \sum k_i=\mathcal{O}(n)。因此总共会有 \mathcal{O}(n) 次 c 数组的修改和扫描线。对于一次扫描线，还会对块内每个元素查询 c_{a_i}。因此在 c 数组上有 \mathcal{O}(n\sqrt n) 次单点查询。所以使用 \mathcal{O}(\sqrt n)-\mathcal{O}(1) 的值域分块维护即可做到 \mathcal{O}(n\sqrt n)。

至于剩下的部分，一次扫描线中扫描 c_x 是 \mathcal{O}(\sqrt n) 时间，删除 0 总数也是 \mathcal{O}(\sqrt n) 个，把她们挂在端点上、链表删除以及清空的总时间也是 \mathcal{O}(\sqrt n)。若当前扫描线中有 q 个询问，则将她们与 \text{cur} 合并以及清空的总时间是 \mathcal{O}(q)。

故一次扫描线的时间是 \mathcal{O}(\sqrt n+q)。\mathcal{O}(n) 次扫描线的总时间复杂度为 \mathcal{O}(n\sqrt n+\sum q)。注意到输入的每个询问只会在她包含的 \mathcal{O}(\sqrt n) 个整块中的某一次扫描线用到，因此对 \sum q 贡献 \mathcal{O}(\sqrt n)。所以扫描线部分的总时间复杂度是 \mathcal{O}(n\sqrt n)。

对于所有 \mathcal{O}(\sqrt n) 个块会枚举所有 \mathcal{O}(n) 个操作。此外还要加入初始的 \mathcal{O}(\sqrt n) 个元素求出初始 c 数组，以及删除所有操作之后的 \mathcal{O}(\sqrt n) 个元素清空 c 数组。这部分时间也是 \mathcal{O}(n\sqrt n)。

所以整个做法的时间复杂度是 \mathcal{O}(n\sqrt n)，空间复杂度为 \mathcal{O}(n)。十分良心不卡常。一发过了。祝毒瘤新年快乐。

AC Link & Code