题目链接：这里

解法：树套树 和 CDQ不会写，分块暴力大法好。

我们可以把原序列a[]分成个块，每个块有个数。然后维护一个b[]，b[]中的每一个块都是一个单调递增的序列。

当前要删除的数为x，所在的块是k，那我们分两种情况做：

1.对于k号块，直接在a[]的k号块中枚举求逆序对，复杂度为。

2.对于除了k号块以外的每一个块，利用b[]二分求x在当前块中产生的逆序对数，复杂度为O(nsqrt(n))

然后删除这个数，把b[]中相对应的数变为0，把这个块重新排序。

因为我们要保证每个块的大小不变，并且每个数所在的块的编号也不变，所以我们在删除的时候不能直接删除。

既然不能直接删除，我们就得搞一些东西来维护。

在计算第一步的时候，我们开一个bool数组f[i]，表示i这个数有没有被删掉，然后枚举的时候判断一下。

在计算第二步的时候，我们开一个数组sum[]，sum[i]表示第i个块里删除了多少个数。这样的话，如果我们在计算的时候这个

块里产生了t对逆序对，而已经被删除的数都变成0，所以每个0都会产生一个逆序对，那么不算上已经被删除的实际只有

t-sum[i]个逆序对。

然后就做完啦。

///BZOJ 3295 动态逆序对

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
//LL ans;
const int maxn = 200010;
int n, m, x, y, num, block, a[maxn], b[maxn], tmp[maxn], belong[maxn], l[maxn], r[maxn], sum[maxn], id[maxn];
bool f[maxn];
LL ans;
int c[maxn];
inline int lowbit(int x){
    return x&-x;
}
void add(int x, int v){
    for(int i=x; i<=n; i+=lowbit(i)) c[i]+=v;
}
int query(int x){
    int res=0;
    for(int i=x; i; i-=lowbit(i)) res+=c[i];
    return res;
}
void init(){
    scanf("%d %d", &n,&m);
    block = sqrt(n);
    num = n/block;
    if(n%block) num++;
    for(int i=1; i<=num; i++) l[i]=(i-1)*block+1,r[i]=i*block;
    r[num]=n;
    for(int i=1; i<=n; i++) belong[i]=(i-1)/block+1;
    for(int i=1; i<=n; i++) scanf("%d", &a[i]), tmp[i]=a[i], id[a[i]]=i;
    ans = 0;
    for(int i=1; i<=n; i++){
        add(a[i],1);
        ans+=1LL*(i-query(a[i]));
    }
    for(int i=1; i<=n; i++) b[i]=a[i];
    for(int i=1; i<=num; i++) sort(b+l[i],b+r[i]+1);
    for(int i=1; i<=n; i++) f[i]=1,sum[i]=0;
}
int query2(int pos, int val){
    int low, high, ret;
    low = l[pos];
    high = r[pos];
    ret = r[pos];
    while(low <= high){
        int mid = (low+high)/2;
        if(b[mid]<=val) ret=mid,low=mid+1;
        else high=mid-1;
    }
    if(b[ret]>val) return l[pos]-1;
    else return ret;
}
int main()
{
    init();
    while(m--){
        printf("%lld\n", ans);
        scanf("%d", &y);
        x = id[y];
        int k = belong[x];
        for(int i=1; i<k; i++){
            ans-=(r[i]-query2(i,a[x]));
        }
        for(int i=k+1; i<=num; i++){
            ans-=query2(i,a[x])-l[i]+1-sum[i];
        }
        for(int i=l[k]; i<x; i++){
            if(f[a[i]]&&a[i]>a[x]) ans--;
        }
        for(int i=x+1; i<=r[k]; i++){
            if(f[a[i]]&&a[i]<a[x]) ans--;
        }
        int pos = query2(k,a[x]);
        b[pos]=0;
        sum[k]++;
        f[a[x]]=0;
        sort(b+l[k],b+r[k]+1);
    }
    return 0;
}