SPOJ 861 - Counting inversions[SWAPS]

张文泰 posted @ 2010年3月26日 16:37 in Art of Science with tags SPOJ 数据结构 , 5073 阅读

题目要求我们时刻维护一个数列的逆序对个数,n在250000的范围内。虽然可能出现的数字总数只有60000(=50000+10000),但是仍然是一个让人头疼的问题。

对于不需要更改的问题,我们可以用多种方法求出其答案。加入了更改操作之后,我们需要维护相关的内容来更新这个值。

我们回忆块状链表的内容,可以配合做出相应的改变。比如,一开始我们用树状数组(Binary Indexed Trees)求逆序对,那么可以产生相应的块状树状数组。我们通过分块维护来降低维护的费用。

这样一来问题就变得比较简单了。需要说明的是,具体编写程序的时候需要在\sqrt{n}的基础上加权分块,不然会出现TLE的问题。


本作品遵循“署名-非商业性使用-相同方式共享 3.0 Unported”协议,转载请注明来自richard-desktop
Creative Commons License
Sandytea 说:
2011年7月06日 10:34

这个为什么用BIT套平衡树会TLE……T_____T


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter