【原题】
3295: [Cqoi2011]动态逆序对
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 778 Solved: 263
[Submit][Status]
Description
对于序列A，它的逆序对数定义为满足
i<
j，且A
i>A
j的数对(
i,
j)的个数。给1到
n的一个排列，按照某种顺序依次删除
m个元素，你的任务是在每次删除一个元素之前统计整个序列的逆序对数。
Input
输入第一行包含两个整数
n和
m，即初始元素的个数和删除的元素个数。以下
n行每行包含一个1到
n之间的正整数，即初始排列。以下
m行每行一个正整数，依次为每次删除的元素。
Output
输出包含
m行，依次为删除每个元素之前，逆序对的个数。
Sample Input
5 4
1
5
3
4
2
5
1
4
2
Sample Output
5
2
2
1
样例解释
(1,5,3,4,2)?(1,3,4,2)?(3,4,2)?(3,2)?(3)。
HINT
N<=100000 M<=50000
【题外话】一直想A了这道题。真累啊！开始的想法是――倒着做，一个一个添加，套一个树状数组，然后每次用平衡树去寻找。显然，现在我只会SPLAY，而且代码长，效率渣。今天和SYF大神一起看hzwer大神的博客，加之哲大爷的一语道破，总算会了树状数组套主席树的方法。
【主要思路】首先用树状数组/归并排序/归并树（时代的眼泪）求出总的序列中的逆序对个数。每次删掉的时候，用树状数组维护位置（1--x-1或x+1--n），并且用权值线段树维护权值信息。
【详细算法】
①在之前的计算总的逆序对个数的时候，我们可以顺带的算出front[i]和back[i]，表示第i个点之前有front[i]个数比他大，之后有back[i]个数比他小。
②起初刚开始做的时候，主席树内部是空的。因此我们要转化――我们本来计算的是删掉某个数后，将会减少所剩的数列中的多少的逆序对（即对所剩的序列产生多少的贡献）；现在我们改成：删掉某个数后，将会对主席树中已经插入的一些节点产生多少的贡献。这样算出来后，用front或back减一下即可。
举个例子。比如有数列5,4,3,2,1，已经删掉了4和1，ans值是3。现在我们要删掉3了。在主席树中，已添加的节点是5和2。通过计算，5,3,2会在3的前面产生一个逆序对，在3的后面产生一个逆序对。而front[3]=2,back[3]=2，那么我们可以知道，ans需要减去front[3]-1与back[3]-1，即最后ans只剩下了1。
③后来套的树状数组具体是怎么实现的呢？比如我们要计算或更新l~r范围内主席树中的某个或某些权值的个数。我们可以转化为计算或更新1--l-1与1--r的前缀，再相减即可。而前缀是可以用树状数组解决的。
【代码】
#include
#include
#define N 100005 #define L(x) (x&-x) using namespace std; typedef long long LL;LL ans; struct arr{int l,r;LL sum;}a[6000000]; int front[N],back[N],c[N],root[N],pos[N],data[N],A[31],B[31]; int n,node,del,x,m,i; inline int ask(int x){int s=0;for (;x;x-=L(x)) s+=c[x];return s;} inline void up(int x){for (;x<=n;x+=L(x)) c[x]++;} inline LL ask_more(int l,int r,int num) { if (l>r) return 0;l--;A[0]=B[0]=0; for (int i=l;i;i-=L(i)) A[++A[0]]=root[i]; for (int i=r;i;i-=L(i)) B[++B[0]]=root[i]; l=1;r=n;LL sum=0; while (l!=r) { int mid=(l+r)>>1; if (num<=mid) { for (int i=1;i<=B[0];i++) sum+=a[a[B[i]].r].sum; for (int i=1;i<=A[0];i++) sum-=a[a[A[i]].r].sum; for (int i=1;i<=B[0];i++) B[i]=a[B[i]].l; for (int i=1;i<=A[0];i++) A[i]=a[A[i]].l; r=mid; } else { for (int i=1;i<=B[0];i++) B[i]=a[B[i]].r; for (int i=1;i<=A[0];i++) A[i]=a[A[i]].r; l=mid+1; } } return sum; } inline LL ask_less(int l,int r,int num) { if (l>r) return 0;l--;A[0]=B[0]=0; for (int i=l;i;i-=L(i)) A[++A[0]]=root[i]; for (int i=r;i;i-=L(i)) B[++B[0]]=root[i]; l=1;r=n;LL sum=0; while (l!=r) { int mid=(l+r)>>1; if (num>mid) { for (int i=1;i<=B[0];i++) sum+=a[a[B[i]].l].sum; for (int i=1;i<=A[0];i++) sum-=a[a[A[i]].l].sum; for (int i=1;i<=B[0];i++) B[i]=a[B[i]].r; for (int i=1;i<=A[0];i++) A[i]=a[A[i]].r; l=mid+1; } else { for (int i=1;i<=B[0];i++) B[i]=a[B[i]].l; for (int i=1;i<=A[0];i++) A[i]=a[A[i]].l; r=mid; } } return sum; } inline void update(int &k,int l,int r) { if (!k) k=++node;a[k].sum++; if (l==r) return; int mid=(l+r)>>1; if (del<=mid) update(a[k].l,l,mid); else update(a[k].r,mid+1,r); } inline int Read() { char ch=getchar();for (;ch<'0'||ch>'9';ch=getchar()); int x=0;for (;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; return x; } int main() { n=Read();m=Read(); for (i=1;i<=n;i++) { data[i]=Read();pos[data[i]]=i; ans+=(front[i]=i-1-ask(data[i]));up(data[i]); } memset(c,0,sizeof(c)); for (i=n;i;i--) back[i]=ask(data[i]-1),up(data[i]); for (i=1;i