【题解】[Ynoi2003] 铃原露露

· · 题解

V 害人不浅啊。

这题是不弱于（或强于）区间逆序对的，所以直接尝试根号做法。而操作分块的做法是不行的，所以去考虑其他形式的分块。

首先注意到答案是可以差分的，并且互不影响。设 f(l,x) 表示区间 [l,x] 中的 a_i 对于 b_x 的贡献，那么就可以表示为 f(1,x) - f(1,l-1)。f(1,x) 的贡献是平凡的，记录每个 b_x 需要计算多少次 f(1,x) 即可，可以随便维护。

之后考虑计算 f(1,l-1) 的贡献，问题就转化成了：每次给出一个区间 [l,r]，对于每个 j \in [l,r]，使 b_j 加上 i \in [1,l-1] 中，a_i \leq a_j 的 i 的个数。这个问题的好处在于查询区间与操作区间不相交，所以每一个 j 受到贡献的区间都是 [1,l-1]。考虑序列分块，设块长为 B。那么对于 [1,l-1] 中的整块部分，每一个整块都对 [l,r] 中的每一个 b_j 造成了贡献，所以可以对于每一个块开一个树状数组，记录这个块对所有 b 的贡献，区间加即可。

进了一步，现在还剩下 [1,l-1] 的散块中对区间 [l,r] 的贡献，不妨设散块为 K。由于散块中数字个数不超过 B，所以 m 个操作的数字个数是 O(mB) 级别的，考虑直接转化成二维数点的形式，但是直接插入的时间复杂度无法接受，考虑换一个角度思考。对于区间 [l,r] 中的整块，受到 a_i \in K 的影响是相同的，所以可以对于每一个序列块开一个支持可插入数点的数据结构，如果对于每一个块开一个值域分块的话，这样的时间复杂度是 O(B^2) - O(B) 的，利用差分+树状数组，可以将时间复杂度平衡到 O(B \log n) - O(B \log n)。直接进行一个点的数即可。

最后是 [1,l-1] 中的散块对 [l,r] 散块的贡献，数字个数不会超过 O(B) 个，可以直接归并统计。

单点查询就会特别简单，只需要将上述几种贡献合并即可。时间复杂度为 O(m (\frac{n}{B} \log n + B \log n))，取 B = \sqrt{n} ，最优时间复杂度为 O(m \sqrt{n} \log n)。