[Ynoi2019] 魔法少女网站

leukocyte · 2021-07-20 23:15:54 · 题解

提供一个好写常数又小的做法。

代码量 2.88 K，最慢点 3s。

容易发现，对于查询操作，我们如果把 \le x 的数设为 1 ，其余为 0 ，那么一个长为 len 的极长 1 连续段的贡献为 \frac{len(len+1)}{2} 。

那么暴力即为从左到右模拟整个过程，维护后缀 1 连续段的长度。

考虑优化这个模拟过程，不难想到序列分块。

设块长为 B ，那么一个块内本质不同的答案只有 O(B) 个。

对于查询区间 [l,r] ，边角暴力。对于中间的块，我们需要维护 \le x 的 1 连续段前缀长度，后缀长度，以及除去前后缀的块内贡献。

如果我们对每个块，从小到大处理每个元素，利用链表或并查集等维护 1 连续段，能做到一次 O(B) 求出一个块所有本质不同的答案。

那么我们预处理直接对块内排序，修改就类似插入排序的方式维护排序后的数组，块内信息暴力重构，那么预处理复杂度是 O(n\log n) ，修改一次复杂度是 O(B) 。

询问对于一个块我们还需要找到 x 的位置，复杂度一次是 O(B+\frac{n}{B}\log B) 。

不难得出 B=\sqrt{n\log n} 最优，总复杂度 O(n\log n+m\sqrt{n\log n}) 。

然而这大概率不能通过这道题，我们继续优化。

注意到瓶颈在于找到 x 在一个块内的位置，这是一个前缀和问题，我们有 O(\sqrt n)-O(1) 的值域分块，而空间限制导致我们不能对每个块开一个前缀和数组，那么容易想到离线，逐块处理，每次利用 O(\sqrt n)-O(1) 的值域分块做到 O(1) 查询位置。

我们来分析复杂度。

预处理不变： O(n\log n) 。

多了新操作每个块的处理： O(\frac{n^2}{B}) 。

修改要增加一个值域分块： O(m(B+\sqrt n)) 。

查询把 \log B 去掉： O(m(B+\frac{n}{B})) 。

那么 B=\sqrt n 最优，总复杂度 O((n+m)\sqrt n) 。