Codeforces 785E Anton and Permutation

Codeforces 785E Anton and Permutation

题目链接

http://codeforces.com/contest/785/problem/E

题目大意

有一个从 $1$ 到 $N$ 的数列 $A$,每次操作选择其中的两个位置,将这两个位置上的数字交换,你需要在每次操作后输出逆序对的个数。

题目分析

考虑将一个数向前移动,会有部分比它大的数,即原本和这个数形成逆序对变成不是逆序对,而比它小的数则到了这个数的后面与它形成逆序对。所以增加的逆序对个数便是比它小的数字的个数减去比它大的数的个数。同样,向后移动增加的逆序对的个数便是比它大的数字的个数减去比它小的数字的个数。于是本题转化为求 $l + 1$ 到 $r – 1$ 中 $A(l)$ 和 $A(r)$ 的排名,于是可以用分块来解决,时间复杂度 $O(N \times \sqrt{N})$。树套树也可以解决这个问题,但是常数比较大,需要注意空间和时间限制。

代码

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

Scroll Up