almost 3 years ago

题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=3295
分析:
本来这道题是树套树的模板题,然而PoPoQQQ提出了一种常数更小(虽然我不认为更好写,工业狗的本质。。)的方法。
我们考虑删去一个数会减少多少个逆序对。
首先我们记录在原序列中只删去这个数会减少个逆序对。
然后对于每次询问减去这个完事。想到这里恭喜你入坑了。。
我们考虑一个逆序对,在删去的时候被减去了一次,在删去的时候又被减去了一次,所以我们要考虑怎么把它加回来。
对于每一个删除操作,设在原序列中的位置,那么我们要考虑之前的操作中有哪些删除的操作使得构成了一个逆序对,把这个值加上就可以了。
那么这个怎么做呢?我们把每一个操作抽象成二维平面上的点,那么对于这个点能构成逆序对的位置就只有左上和右下区域。又考虑到操作之间的时间先后关系,我们可以用分治搞定时间,然后归并成递增的序列,然后再树状数组区间求和即可。
这个时间复杂度是,然而常数比较小,我竟然跑到了,蛤蛤。
bzoj3295.cpp

← bzoj1065:[NOI2008]奥运物流 bzoj1066:[SCOI2007]蜥蜴 →
 
comments powered by Disqus