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
1
5
3
4
2
5
1
4
2
Sample Output
5
2
2
1
Solution
给每个被删除的元素打一个删除时间$t$，设下标为$x$，权值为$y$，那么删除一个元素后，减少的逆序对个数为：
1、$t$比它大，$x$比它小，$y$比它大。
2、$t$比它大，$x$比它大，$y$比它小。
$CDQ$统计一下就好了……
读错题把删除元素看成删除下标真的智障。
Code
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define N (100009)
#define LL long long
using namespace std; struct Que
{
int x,y,t;
bool operator < (const Que &a) const
{
return t>a.t;
}
}a[N],tmp[N]; int n,m,c[N],q[N],ans[N],pos[N];
LL sum; inline int read()
{
int x=,w=; char c=getchar();
while (c<'' || c>'') {if (c=='-') w=-; c=getchar();}
while (c>='' && c<='') x=x*+c-'', c=getchar();
return x*w;
} void Update(int x,int k)
{
for (; x<=n; x+=(x&-x)) c[x]+=k;
} int Query(int x)
{
int ans=;
for (; x; x-=(x&-x)) ans+=c[x];
return ans;
} void CDQ1(int l,int r)
{
if (l==r) return;
int mid=(l+r)>>;
CDQ1(l,mid); CDQ1(mid+,r);
int i=l,j=mid+,k=l-;
while (i<=mid || j<=r)
if (j>r || i<=mid && a[i].x<a[j].x)
{
Update(a[i].y,);
tmp[++k]=a[i]; ++i;
}
else
{
ans[a[j].y]+=Query(n)-Query(a[j].y);
tmp[++k]=a[j]; ++j;
}
for (int i=l; i<=mid; ++i) Update(a[i].y,-);
for (int i=l; i<=r; ++i) a[i]=tmp[i];
} void CDQ2(int l,int r)
{
if (l==r) return;
int mid=(l+r)>>;
CDQ2(l,mid); CDQ2(mid+,r);
int i=l,j=mid+,k=l-;
while (i<=mid || j<=r)
if (j>r || i<=mid && a[i].x>a[j].x)
{
Update(a[i].y,);
tmp[++k]=a[i]; ++i;
}
else
{
ans[a[j].y]+=Query(a[j].y-);
tmp[++k]=a[j]; ++j;
}
for (int i=l; i<=mid; ++i) Update(a[i].y,-);
for (int i=l; i<=r; ++i) a[i]=tmp[i];
} int main()
{
n=read(); m=read();
for (int i=; i<=n; ++i) a[i].x=i, a[i].y=read(), pos[a[i].y]=i;
for (int i=; i<=m; ++i) a[pos[q[i]=read()]].t=i;
for (int i=; i<=n; ++i) if (!a[i].t) a[i].t=m+; for (int i=; i<=n; ++i) sum+=Query(n)-Query(a[i].y), Update(a[i].y,);
for (int i=; i<=n; ++i) Update(a[i].y,-);
sort(a+,a+n+); CDQ1(,n);
sort(a+,a+n+); CDQ2(,n); for (int i=; i<=m; ++i) printf("%lld\n",sum), sum-=ans[q[i]];
}