例题
P3157 [CQOI2011] 动态逆序对
-
题意略。
-
一开始想了半天，老半天的前后缀主席树做法（分别对前后缀开桶，模仿树状数组求逆序对，算贡献），最后还是发现似乎没办法统计算重的贡献，因为得维护被删掉的点中有多少个下标小且值大或下标大且值小，而且这玩意等效在线。
-
故还是来考虑一下 CDQ...我们称一个逆序对 \((i,j)\)“属于 \(i\)”，当且仅当 \(t_i<t_j\)，这里 \(t_x\) 是第 \(x\) 个元素被删除的时间。对于未被删除的元素，认为 \(t_x=+\infty\)。
-
于是问题变成求初始序列的逆序对数量和属于每个 \(i\) 的逆序对数量。那么看到这里的属于其实就是 \(([i<j] \oplus [a_i<a_j]) \And t_i<t_j\) 这一三维偏序问题，显然可 CDQ。
-
首先可以认为是按下标排序，然后套归并的壳子，每次合并的时候维护一下归属就好，实际实现中我的做法是用树状数组当桶储存对面的删除时刻。
-
复杂度 \(O(n\log^2)\)，一只 \(\log\) 是归并，一只是树状数组，常数稍大。