BZOJ 3295 [Cqoi2011] 动态逆序对

发布于 2017-09-11  136 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=3295

题意:给 1 到 n 的一个排列,按照某种顺序依次删除 m 个元素,你的任务是在每次删除一个元素之前统计整个序列的逆序对数。


调了将近 2h... 我好菜啊.jpg

就不细说了 T.T,大概思路是将删点变成加点,对每个数多维护一个加入时间,就是一个三维偏序问题的模型了。正反两边 CDQ 即可。

都是排列不用判重真是好评啊 T.T

 


一个非常弱的准退役OIER