BZOJ2141 排队

题目传送门

Solution:

这就是一个裸的动态逆序对问题,对于每一次交换,可以看作是先删掉一个数,再删一个数,然后加入一个数,再加入一个数,所以只要解决插入和删除就可以了。对于删除,我们只需要知道在x前面有几个数比它大,在它后面有几个数比它小。对于插入,我们也只需要知道在x前面有几个数比它大,在它后面有几个数比它小。然后就可以维护逆序对的数量了。这个可以用树套树来完成,外层树状数组表示位置为1~i的前缀和,内层线段树表示权值在l~r的数的个数。

code:

3 条评论
  1. %%%
    我不会这道裸题

  2. I precisely wanted to appreciate you all over again. I am not sure what I would have carried out without these ideas revealed by you about such a subject matter. It had become a real scary dilemma in my view, however , considering a new specialized technique you solved it made me to weep for gladness. I’m happier for your assistance and have high hopes you know what an amazing job that you are carrying out training some other people all through your blog. Probably you’ve never encountered all of us.

  3. Thanks so much for giving everyone such a memorable possiblity to read critical reviews from this website. It is always very fantastic and packed with a lot of fun for me personally and my office colleagues to search your site minimum 3 times per week to read the new tips you have. And indeed, I am also actually happy with the brilliant pointers you give. Some 2 areas in this posting are without a doubt the simplest I have ever had.

发表一条评论