每次可以删除一个点，求每次删除之前的逆序对。
可以用CDQ分治的方法：
题意是删除点，可以倒过来，逆序 每次加一个点进去，而每个点加进去对逆序对的影响就是加上前面的比它大的数和后面的比它小的数。
对于普通的逆序对，我们可以用二维的坐标来表示
x：1，2，3，.... （点在序列中的位置）
y：a[1],a[2],a[3],... （点的值）
我们要找的逆序对其实就是所有满足x[i]<x[j] && a[i]>a[j]的i，j。
在这道题中，其实就是加入了一维时间（加点的顺序）。
将坐标变成了
n：1，2，3，....（加点的顺序，时间维）
x:pos[1],pos[2],pos[3].....（当前加入的点在序列中的位置）
y:a[1],a[2],a[3].....（点的值）
这道题就转化成了一道三维偏序的问题，每次按照时间顺序加入一个点，统计在它左上角的点（即在它的左边并且值比它大）和右下角的点（即在它的右边并且值比它小）的总数，就是当前点对逆序对的贡献。
如何得到三个坐标？
时间维x：可以先把要删除的点读进来，然后将没有删除的点按顺序加上时间维（一维坐标x），再逆序给删除的点加上时间维（一维坐标x）。
序列中的位置y：用pos[i]记录值为a[i]的点的位置。
点的值z：直接用a[i]赋值即可。
把三个坐标做好了，就可以用三维偏序的思想来解题了。
这样，做两次CDQ就行了，一次统计左上角的点，一次统计右下角的点。
CDQ的思路：
void CDQ（l,r)
{
if(l==r)return ;
CDQ(l,mid)
solve(l,r) //利用左区间更新右区间。
CDQ(mid+1,r)
}
如何更新？
以统计左上角为例：
分别将左右区间按照y排序，每次统计右区间的一个点的时候，把左区间y小于右区间这个点y的全部加进去，因为事先两个区间都排好了序，所以加的时候不会重复添加。设左区间满足条件的点为i，右区间的点为j，将i的z坐标作为下标，1作为值加入到树状数组，所有满足条件的i都加进去后，统计区间（j[z]+1,n)的和，累加到记录的数组中。
更新完成后，要将修改过的点还原（修改过哪些还原哪些），并且将整个区间重新按照x排序。
如何得出答案？
假如用f[i]记录左上角的点，g[i]记录右下角的点，则先分别对f[i],g[i]求前缀和再将f[i]和g[i]相加就得到了加入这个点时的逆序对，以z[i]作为索引将答案记录下来，之后，只要按照操作的顺序输出结果就行了（因为操作给的是点的值，所以用z作为索引很方便）。
注意是多组数据，要初始化数组。
代码如下：
#include<bits/stdc++.h>
#define rep(i,n) for(i=1;i<=n;i++)
#define creatmid int mid=(l+r)>>1
using namespace std;
const int maxn=200100;
typedef long long int ll;
ll tree[maxn],ou[maxn],f[maxn],g[maxn];
int a[maxn],b[maxn],pos[maxn];
bool tag[maxn];
struct zz{int x,y,z;}nd[maxn];
int n,m;
int getint()
{
char c;int x;
for(c=getchar();!isdigit(c);c=getchar());
for(x=0;isdigit(c);c=getchar())
x=(x<<1)+(x<<3)+c-‘0‘;
return x;
}
int lowbit(int x)
{
return (x&(-x));
}
void init()
{
memset(tag,0,sizeof(tag));
memset(f,0,sizeof(f));
memset(g,0,sizeof(g));
int i;
rep(i,n)
{
//scanf("%d",&a[i]);
a[i]=getint();
pos[a[i]]=i;
}
rep(i,m)
{
//scanf("%d",&b[i]);
b[i]=getint();
tag[b[i]]=true;
}
int num=0;
rep(i,n)
if(!tag[a[i]])
{
nd[++num].x=num;
nd[num].y=pos[a[i]];
nd[num].z=a[i];
}
for(i=m;i>0;i--)
{
nd[++num].x=num;
nd[num].y=pos[b[i]];
nd[num].z=b[i];
}
}
bool compx(const zz&i,const zz&j)
{
return i.x<j.x;
}
bool compy(const zz&i,const zz&j)
{
return i.y<j.y;
}
void update(int p,int add)
{
for(int i=p;i<=n;i+=lowbit(i))
tree[i]+=add;
}
ll query(int p)
{
ll ans=0;
for(int i=p;i>0;i-=lowbit(i))
ans+=tree[i];
return ans;
}
void solve1(int l,int r)
{
creatmid;
int i,j;
sort(nd+l,nd+mid+1,compy);
sort(nd+mid+1,nd+r+1,compy);
for(i=l,j=mid+1;j<=r;j++)
{
while(nd[i].y<nd[j].y && i<=mid)
{
update(nd[i].z,1);
++i;
}
f[nd[j].x]+=query(n)-query(nd[j].z);
}
for(j=l;j<i;j++)update(nd[j].z,-1);
sort(nd+l,nd+r+1,compx);
}
void solve2(int l,int r)
{
creatmid;
int i,j;
sort(nd+l,nd+mid+1,compy);
sort(nd+mid+1,nd+r+1,compy);
for(i=mid,j=r;j>mid;j--)
{
while(nd[i].y>nd[j].y && i>=l)
{
update(nd[i].z,1);
--i;
}
g[nd[j].x]+=query(nd[j].z-1);
}
for(j=mid;j>i;j--)update(nd[j].z,-1);
sort(nd+l,nd+r+1,compx);
}
void CDQ1(int l,int r)
{
if(l==r)return ;
creatmid;
CDQ1(l,mid);
solve1(l,r);
CDQ1(mid+1,r);
}
void CDQ2(int l,int r)
{
if(l==r)return ;
creatmid;
CDQ2(l,mid);
solve2(l,r);
CDQ2(mid+1,r);
}
int main()
{
// freopen("F.in","r",stdin);
// freopen("F.out","w",stdout);
//ios::sync_with_stdio(false);
while(scanf("%d%d",&n,&m)!=EOF)
{
init();
sort(nd+1,nd+n+1,compx);
CDQ1(1,n);
CDQ2(1,n);
int i;
rep(i,n)
{
f[i]+=f[i-1];
g[i]+=g[i-1];
}
rep(i,n)
{
ou[nd[i].z]=f[i]+g[i];
}
rep(i,m)
printf("%lld\n",ou[b[i]]);
}
}
原文：http://www.cnblogs.com/xionglinlin/p/5041192.html