题解P6578 [Ynoi2019] 魔法少女网站

· · 题解

题目

P6578 [Ynoi2019] 魔法少女网站

第十分块。

分析

（主要介绍怎么想到要使用这些做法的，以及这些做法的一点特性）

操作分块+序列分块。

首先我们考虑一下不用修改的话应该怎么做。

我们可以把题目这样转化：假设 x 目前给定，设 b[i]=(a[i]\geq x) ，那么我们现在的问题就是询问区间所有为 1 的极长子区间的 siz*(siz+1)/2 之和。

那么现在 x 不给定了，相当于就是我们每次会修改一些点 0->1 或者 1->0 。

我们发现 1->0 的情况很不好维护，而 0->1 的话就相当于是合并区间或者在区间左端或者右端单点增加了（这里要分类讨论几种情况）。

那怎么让只有 0->1 的情况呢？ 我们可以考虑直接把询问按照 x 升序排序，然后我们发现这个满足的数会越来越多，这样就保证了。

好了，现在我们的问题就是怎么来维护这个极长子区间呢？

考虑序列分块/链表，这里使用序列分块，同时还要记录修改，因为一会要撤回（至于为什么要撤回见后文）。

那么现在我们解决了不带修改的问题，带修改的呢？

我们不可能直接修改，因为这样依然会是我们每次会修改一些点 0->1 或者 1->0 。

这个时候的 1->0 没办法再用所谓的排序规避掉了。

那么我们可以这样来考虑：我们先不修改，把需要修改的那些点先存下来，然后把剩下的一直没有修改的点按照静态做法来做。

接下来我们对于修改了的点考虑，由于我们默认的是 0 ，于是我们现在可以对于每一次询问暴力遍历所有的修改，然后暴力判断查看这个修改会不会让我们的某一个位置 0->1 ，是就改，不是就不管。

那么这样的话时间复杂度直接爆炸，是 O(n^2) 的（假设 n,m 同阶）。

那现在就需要一个新的技巧了：操作分块。

操作分块可以让我们当前的全局修改只有 O(B) 级别，而代价是增加一个每次处理当前所有块修改的复杂度，是 O(\frac{m}{B}\times重构复杂度 ) 。

那么现在我们对操作分块，我们的修改只有 O(B) 个了（就相当于块内修改的个数），于是我们可以使用刚刚的对于每一个询问遍历所有修改的影响的办法了。

操作分块具体实现来就是刚刚说的每个询问遍历所有修改然后处理，再撤回到这个询问遍历所有修改之前的那个状态就可以了。

取块长 B=\sqrt{n} ，这样做时间复杂度就是 O(n\sqrt{n}) 的（假设 n,m 同阶），实际测试序列分块取块长 \sqrt{\frac{3}{4}n} ，操作分块取 \sqrt{14m} 要快一点。

代码

请务必做好卡常的心理准备...

卡了一万年的常...人都傻了...

可以参考 Qiuly 的代码，思路是一样的/kk。