区间排序区间逆序对

· · 算法·理论

区间排序区间逆序对。

UPD：我值域块间那里就是直接把区间视为等价类，就是对查询的所有端点离散化之后得到段，我并不知道这么描述等价类是否妥当，如果不妥当请自动将等价类分治视为普通分治。同时，该部分存在使用 odt+sgt 结构做到相同复杂度的方法，但是常数会大一些，具体可见 这个 和 这个。

UPD：经过改良后做法已经与 pri 关联不大，但是仍然有启示意义。注意本做法与值域分块关联性更大，操作分块可以使用 odt+sgt 代替。

考虑到我再不发这个逆序对相关问题就要被 yangzichen1203 抢光了，所以还是来发一个。默认是排列。做法类似 pri。做法只口胡没有写，所以要是假了请指出。是在不想写了太屎了。听不懂我在说什么的先去看 pri。

首先值域分块块长 B。

值域块内

省流：逆序对数最多 O(nB)，还单调不增，所以随便单 \log 维护一下就行了。

查询值域块之内的贡献。预处理是 O(nB) 没必要说。逆序对至多 O(nB) 对，且每次排序时只会去除逆序对不会加入逆序对，所以暴力维护逆序对均摊 O(nB)。具体就是模拟插入排序，假设前 i 个排好序了，对下一个像前面不断交换直到合法。注意你可以只交换相邻两个，复杂度依然对。先不考虑常数。但比较不能暴力一个个点扫过去判断是否向前，否则复杂度线性。需要维护一个线段树二分到第一个不满足 a_i<a_{i+1} 的位置，然后再暴力向前交换。这样总复杂度 O(nB\log{B}) 因为你要线段树带上 \log（可能不需要，我没仔细想），然后每次还要扫每个值域块线段树二分，单次 O(\frac{n}{B}\log{B})。还需要快速获取每个点所在的序列的下标，这个相当于 O(\frac{n}{B}) 次区间推平（因为每次排序是把一段区间里面介于一个值域块里的数提到一些连续的序列位置，被值域块划分出 O(\frac{n}{B}) 个连续段，所以总数 O(\frac{n}{B}) 次把一段连续区间赋值为一个原序列的下标），并支持单点查询下标。也就是 O((\frac{n}{B}+B)\log{B})。

还没好呢。我们相当于 O(nB) 次加入一对二元组 (i,j)，查询被区间 (l,r) 包含的 (i,j) 数量。那么你当然可以离线扫描线带上 \log，但可以写根号平衡（二维分块）做到 O(nB+n\sqrt{n})。

值域块间

省流：操作分块。块间相当于对值域块进行重新分配（重点在重新分配），然后套上等价类分治优化查询的过程即可。

操作分块块长 S。令 f_i,_j 表示第 i 个操作分块出来的连续段（等价类）有几个数落在第 j 个值域块内。

也就是查询连续段之间，值域块之间的贡献。这个比较简单。查询一下就对全局前缀和做到 O(\frac{nS}{B})。这个是暴力。套上 tb5 即可做到整体 O(\frac{nS\log{S}}{B})。这里说一下怎么 tb5。

需要有一种能在 O(\frac{n}{B}) 时间里支持修改的做法，这样修改 len 次才能做到 O(\frac{nlen}{B})。要修改就是扫描修改区间里所有值域块，定义 w_i 表示第 i 个值域块在当前修改的区间里有几个数。那么只需要按照值从小到大，一个一个块分配即可。看起来是 O(\frac{nS^2}{B}) 然而势能分析可以搞成 O(\frac{nS}{B})，如果你理解了怎什么是重新分配 w 数组，你会知道修改一次最多增加 O(\frac{n}{B}+S) 个非 0 值域块，具体的你记录每个序列段的起点终点，修改时只对这个连续段改一改就好了。那么 T(x)=2T(\frac{x}{2})+O(x^2+\frac{nS}{B})，所以这里总体是 O(\frac{nS\log{S}}{B}+S^2)。

做完了。复杂度 O(\frac{n}{S}(\frac{nS\log{S}}{B}+S^2)+nB\log{B}+\frac{n^2}{B}\log{B}+n\sqrt{n})=n\sqrt{n}\log{n}。

感觉难以去 \log，但是经过思考后感觉很对。有空回来写代码。

UPD：唐飞了，值域块内的势能分析可以提到全局上。已经修改了。

非常荣幸攻克又一个逆序对问题。如果早就有人完成了这个，请指出我的落后与愚蠢。