题解：P11367 [Ynoi2024] 魔法少女网站第二部

无名之雾 · 2024-12-18 20:11:42 · 题解

lxl 讲课作业里的可爱的 Ynoi。

分治，考虑每次处理跨过区间中点的询问。左右区间互相的影响形式形如：“若右区间包含一个 [x,y] 内的数，则答案变化量为 \Delta。”注意左右区间包含了哪些数仅跟一个端点有关，所以类似于区间数点的形式，可以考虑离线维护。

我们以计算左区间产生的 \Delta 为例。枚举左区间端点 r\le p\le l，用 set 之类的东西暴力维护左区间前驱后继。

我们现在加入 a_p，设其前驱为 x，后继为 y，内部贡献计算。

对于跨区间的影响，我们得到了两个新的 x\rightarrow a_p 以及 a_p\rightarrow y，我们考虑去掉了一个旧的 x\rightarrow y。

分别找到右区间第一个能把这个所谓的类指针物体断开的数的位置 k，把对应的变化量挂在 k 位置。然后枚举左端点为 p 的询问，将询问对应的右端点及其左侧的所有断开数的变化量都计入询问答案。右区间也做类似的事情即可。

复杂度是 \mathcal O(n\log^2 n)。

使用多叉线段树优化后复杂度可以做到 \mathcal O(\dfrac{n\log^2 n}{\log \log n})。