题意

给出一个排列,每次删除排列中的一个数,求每次删除前排列中的逆序对数量。

分析

每次删除一个数,我们将操作逆向,变成了从初始的状态,每次插入一个数,求插入以后的逆序对数量。

可以通过考虑每次插入一个数以后逆序对数量的变化来得到。

利用三维偏序 (操作编号,插入的数 \(x\),插入数的位置 \(y\)),我们对于每一个 \((x,y)\) ,就是要找操作编号在 \((x,y)\) 之前的数对,且满足 \(a<x,b>y\) 或者 \(a>x,b<y\) 的个数。

同样可以转换成二维平面数点问题,第二维利用归并排序排序,第三维用树状数组维护。

对于两种不同的情况,满足 \(a<x,b>y\) 或者 \(a>x,b<y\) 做两次即可。

 


发表评论

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