Description
对于序列\(A\)，它的逆序对数定义为满足\(i<j\)，且\(A_i>A_j\)的数对\((i,j)\)的个数。给\(1\)到\(n\)的一个排列，按照某种顺序依次删除\(m\)个元素，你的任务是在每次删除一个元素之前统计整个序列的逆序对数。
Input
输入第一行包含两个整数\(n\)和\(m\)，即初始元素的个数和删除的元素个数。以下\(n\)行每行包含一个\(1\)到\(n\)之间的正整数，即初始排列。以下\(m\)行每行一个正整数，依次为每次删除的元素。
Output
输出包含$m$行，依次为删除每个元素之前，逆序对的个数。
HINT
$n \leq 100000$ $m \leq 50000$
这道题做法很多……但是我来做这道题只是为了练CDQ分治的……
首先，我们可以考虑当删除一个数之后逆序对数减少了多少。不难发现，减少的逆序对数就是 这个数 前面比它大的数的个数 加上 后面比它小的数的个数。
那么，如果我们强行把最后数列中剩下的数也删掉，那么我们就得到了$n$个操作，用 $(x_i,y_i,z_i)$ 表示操作$i$是在时刻$z$把$y$位置上值为$x$的数给删掉。
于是，对于一个操作$i$，这个操作减少的逆序对数为 $x_j>x_i,y_j<y_i,z_j>z_i$以及$x_j<x_i,y_j>y_i,z_j>z_i$的$j$的个数。
其实这就是一个三维偏序。对于两个式子分别在CDQ分治的时候扫一遍即可。 大概的思路就是排序一维，分治时归并一维，剩下一维再用树状数组来维护。
下面贴代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
#define maxn 100010 using namespace std;
typedef long long llg; struct data{
int x,y,b;
bool operator < (const data &h)const{return x>h.x;}
}s[maxn],ss[maxn];
int c[maxn],n,m,a[maxn],ans[maxn];
bool w[maxn]; llg ana; int getint(){
int w=;bool q=;
char c=getchar();
while((c>''||c<'')&&c!='-') c=getchar();
if(c=='-') c=getchar(),q=;
while(c>=''&&c<='') w=w*+c-'',c=getchar();
return q?-w:w;
} void add(int x,int y){while(x<=n) c[x]+=y,x+=x&(-x);}
int sum(int x){
int t=;
while(x) t+=c[x],x-=x&(-x);
return t;
} void solve(int l,int r){
if(l>=r) return;
int mid=l+r>>,now=l,kk=l-,k1=l,k2=mid+;
solve(l,mid); solve(mid+,r);
for(int i=mid+;i<=r;i++){
while(s[now].y<s[i].y && now<=mid) add(s[now].b,),now++;
ans[s[i].b]+=sum(n)-sum(s[i].b);
}
for(int i=l;i<now;i++) add(s[i].b,-);
now=r;
for(int i=mid;i>=l;i--){
while(s[now].y>s[i].y && now>mid) add(s[now].b,),now--;
ans[s[i].b]+=sum(n)-sum(s[i].b);
}
for(int i=now+;i<=r;i++) add(s[i].b,-);
while(k1<=mid && k2<=r)
if(s[k1].y<s[k2].y) ss[++kk]=s[k1++];
else ss[++kk]=s[k2++];
while(k1<=mid) ss[++kk]=s[k1++];
while(k2<=r) ss[++kk]=s[k2++];
for(int i=l;i<=r;i++) s[i]=ss[i];
} int main(){
File("a");
n=getint(); m=getint();
for(int i=;i<=n;i++) a[getint()]=i;
for(int i=;i<=m;i++){
s[i].x=getint(); s[i].b=i;
s[i].y=a[s[i].x]; w[s[i].x]=;
}
for(int i=,t=m;i<=n;i++)
if(!w[i]){
s[++t].x=i; s[t].b=t;
s[t].y=a[s[t].x];
}
sort(s+,s+n+); solve(,n);
for(int i=;i<=n;i++) ana+=ans[i];
for(int i=;i<=m;i++){
printf("%lld\n",ana);
ana-=ans[i];
}
}