BZOJ3295: [Cqoi2011]动态逆序对（带修主席树）

3295: [Cqoi2011]动态逆序对
**Time Limit: 10 Sec Memory Limit: 128 MB
Description
对于序列A，它的逆序对数定义为满足$i<j$，且Ai>Aj的数对(i,j)的个数。给1到n的一个排列，按照某种顺序依次删
除m个元素，你的任务是在每次删除一个元素之前统计整个序列的逆序对数
Input
输入第一行包含两个整数n和m，即初始元素的个数和删除的元素个数。
以下n行每行包含一个1到n之间的正整数，即初始排列。
以下m行每行一个正整数，依次为每次删除的元素。
N<=100000 M<=50000
Output
输出包含m行，依次为删除每个元素之前，逆序对的个数。
Sample Input
5 4
1
5
3
4
2
5
1
4
2
Sample Output
5
2
2
1
样例解释
KaTeX parse error: Unexpected character: '' at position 12: (1,5,3,4,2)̲(1,3,4,2)(3,4,…。

这道题显然是一道带修改主席树（或者cdq分治），主要讲讲如何用带修改主席树来解决这个问题。

首先各位大佬要先保证自己会用树状数组求逆序对，这样我们可以求出最开始的答案值（当然你用线段树，cdq分治，归并排序写也可以，只是码量相对较大）。想用知道cdq分治求逆序对的原理的请戳这里。

那么我们思考一下，如果我们知道上一次的答案，我们只需要计算出这一次修改的差量即可，怎么计算差量呢？我们知道，如果第$i$个数被删除了，那么逆序对总数会减少在$i$之前没被删除的且比$a_i$大的数的总数加上在$i$之后没被删除的且比$a_i$小的数的总数。不难看出这两个量是一种对称的关系，这样的话我们只用思考其中一种情况。

$So$，如何维护在$i$之前没被删除的且比$a_{}$

最后

以上就是老迟到纸鹤为你收集整理的BZOJ3295: [Cqoi2011]动态逆序对（带修主席树）的全部内容，希望文章能够帮你解决BZOJ3295: [Cqoi2011]动态逆序对（带修主席树）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。