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
    
     #include
     
      #include
      
       #include
       
        #include
        
         #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\n",Ans);    for (int i=1;i