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
没有删除就直接树状数组了事，但是有删除操作呢？
每次删数必定是记录其后面有多少个比它小的数，前面有多少个比它大的数
这个东西我们能用带修改主席树维护
每次删点需要清除其对之后的影响，这样的话我们可以用树状数组维护位置，用动态开点带修改主席树维护权值，然后这题就完了。。。
其实我也不知道那个到底叫带修改主席树还是叫线段树。。。
/*program from Wolfycz*/
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define inf 0x7f7f7f7f
#define lowbit(x) ((x)&(-x))
using namespace std;
typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
inline char gc(){
static char buf[1000000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;
}
inline int frd(){
int x=0,f=1; char ch=gc();
for (;ch<'0'||ch>'9';ch=gc()) if (ch=='-') f=-1;
for (;ch>='0'&&ch<='9';ch=gc()) x=(x<<3)+(x<<1)+ch-'0';
return x*f;
}
inline int read(){
int x=0,f=1; char ch=getchar();
for (;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=-1;
for (;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+ch-'0';
return x*f;
}
inline void print(int x){
if (x<0) putchar('-'),x=-x;
if (x>9) print(x/10);
putchar(x%10+'0');
}
const int N=1e5,M=3e7;
int v[N+10],pos[N+10],root[N+10],A[N+10],B[N+10];
int ls[M+10],rs[M+10],cnt[M+10];
int n,m,tot;
void Modify(int &p,int l,int r,int x,int v){
if (!p) p=++tot;
cnt[p]+=v;
if (l==r) return;
int mid=(l+r)>>1;
if (x<=mid) Modify(ls[p],l,mid,x,v);
else Modify(rs[p],mid+1,r,x,v);
}
int query(int l,int r,int x,int mode){
if (l>r) return 0;
int res=0,cnta=0,cntb=0;
for (int i=l-1;i;i-=lowbit(i)) A[++cnta]=root[i];
for (int i=r;i;i-=lowbit(i)) B[++cntb]=root[i];
l=1,r=n;
while (l!=r){
int mid=(l+r)>>1;
if (x<=mid){
if (mode==1){
for (int i=1;i<=cnta;i++) res-=cnt[rs[A[i]]];
for (int i=1;i<=cntb;i++) res+=cnt[rs[B[i]]];
}
for (int i=1;i<=cnta;i++) A[i]=ls[A[i]];
for (int i=1;i<=cntb;i++) B[i]=ls[B[i]];
r=mid;
}else{
if (mode==0){
for (int i=1;i<=cnta;i++) res-=cnt[ls[A[i]]];
for (int i=1;i<=cntb;i++) res+=cnt[ls[B[i]]];
}
for (int i=1;i<=cnta;i++) A[i]=rs[A[i]];
for (int i=1;i<=cntb;i++) B[i]=rs[B[i]];
l=mid+1;
}
}
return res;
}
int main(){
n=read(),m=read(); ll Ans=0;
for (int i=1;i<=n;i++){
v[i]=read(); pos[v[i]]=i;
Ans+=query(1,i-1,v[i],1);
for (int j=i;j<=n;j+=lowbit(j)) Modify(root[j],1,n,v[i],1);
}
printf("%lld
",Ans);
for (int i=1;i<m;i++){
int x=read(); ll res=0;
res+=query(1,pos[x]-1,x,1);
res+=query(pos[x]+1,n,x,0);
printf("%lld
",Ans-=res);
for (int j=pos[x];j<=n;j+=lowbit(j)) Modify(root[j],1,n,x,-1);
}read();
return 0;
}