BZOJ 3295 [Cqoi2011] 动态逆序对


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

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


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

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

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

 

声明:zgz233|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - BZOJ 3295 [Cqoi2011] 动态逆序对


一个oier的博客 |注册功能过几天就修| 博客搬家啦,现在跑的飞快!

标签: , ,