mobai

Neutralized · 2023-05-20 07:59:05 · 个人记录

牛逼题，贺的强大 O((n+q) \sqrt{n}) 做法（。

很有根号智慧 /hs /bx

先把 b_i \leftarrow i-1-b_i，也就是变成 j \lt i \land a_j \lt a_i 的个数。

首先限制肯定是后面的优先级更高，于是有以下两种求出排列的方法：

观察法二到底在干什么，其实就是把后面可能的贡献放到一起再由被转移者自行取出会转移到它的贡献（，那么这两种方法事实上就是在做同一件事情，于是可以把它们缝起来交叉使用，正确性没有问题。

考虑这两种方法各自的特征：法一比较适合暴力（？，法二则可以轻易地（？）预处理、合并前后两段区间的答案（合并 A,B 时，A 的每个值会保持相对顺序变为 B 中选剩下的值，这是可以双指针的），那么就可以分块，对散块应用法一，对整块预处理从 R_i 扫到 L_i 后 已经选走的 每个值以及对应的位置（按值升序放在 vector 里）（考虑如何预处理：我们直接扫 i = R \sim L，每次暴力地归并 (b_i + 1, i) 和后面的集合，这样做总复杂度是 O(B^2 \dfrac{n}{B}) = O(nB)）。考虑某一块每两次修改之间的所有询问，将它们挂在这一块上和维护的已取值集合一起归并，每个询问只会被挂到 O(\dfrac{n}{B}) 个块上，每次归并每个询问会贡献 O(1)，那么复杂度就是 O((n+q) \dfrac{n}{B}) 的。注意这里我们还需要对每一块上挂的询问按值升序排序，考虑修改是单点修改，那么所有块 “每两次修改” 的个数总和就是 O(q)，于是我们可以以 B 为底使用 O(B + |S|) 的基数排序，这里的 \sum |S| = q，复杂度是 O(q (\dfrac{n}{B} + B))。

然后考虑每次修改怎么维护这一块的已取值集合，由于我们有一个双指针做到 O(|A| + |B|) 的合并方法，所以你可以暴力地把要修改的元素从 vector 里分离出来，改完再合并分出来的三段，复杂度还是 O(q B)。

所以总复杂度就是 O((n + q) (\dfrac{n}{B} + B))，块长直接取 O(\sqrt{n}) 就可以 O((n+q) \sqrt{n}) 了。

由于要挂询问，不妨离线对每个块分别处理（块间的贡献不是立即要求的）。

注意下标不要搞混了 /yun，以及对于询问需要从 x+1 开始转移，所以提前 ++x 就好了。