类似排序那题,但是按照原来的做法只有部分分。
线段树分裂合并会 T 成 70。
有一个很骚的做法:模拟冒泡的过程。
冒泡的思想是依次交换相邻的逆序对,要做 O(n2) 次。
因此我们用线段树维护一个区间内第一组相邻的逆序对。
实际上很好维护,对于一个位置 i,如果 ai>ai+1,则在线段树上把这个位置修改成 i,否则为正无穷。
区间查询就是一个区间最小值的过程。
对于一个操作,我们一直找该区间内的相邻逆序对,对于一组相邻逆序对 (x,x+1),我们按如下几步处理: 1. 交换 ax,ax+1。 2. 删除线段树上位置 x 的逆序对。 3. 更新新的 ax 对 ax−1 的贡献。 4. 更新 ax+2 对新的 ax+1 的贡献。
最多交换 O(n2) 次,总复杂度 O((n2+m)logn),可以承受。
代码:
1 |
|