[CQOI2011] 动态逆序对

使用树状数组求出初态下出f[i]、g[i]表示位置小（大）于i且值大（小）于a[i]的元素个数。显然ans|初=sum f[i]=sum g[i]。

考虑第一个删去的点x，删去以后，ans减少f[x]+g[x]；再考虑第二个删去的点y，删去以后，ans减少f[y]+g[y]？不，f[y]、g[y]中可能算上了x（此题里是必然），这{x，y}这一对已经在上一次删除时减掉了，所以ans减少f[y]+g[y]的同时，还应加上已删除的点中与y构成的“逆序对数”。以后删除的点同理；

假设当前正在删除元素x，设元素到位置的映射为id[x]，设f1、g1为在已删的点中与x相比位置小（大）于i且值更大（小）于的点的个数，那么ans应该为ans-f[x]-g[x]+f1+g1。现考虑如何快速计算f1、g1。以计算f1为例：

一：将删除的点放在新序列b的相应位置，每次扫描b[1~id[x]]中有多少满足b[i]>x的点。
二：不放将序列b扩充为矩阵b[i,j]，b[i,j]表示位置为i，值为j的元素是否已经被删除。每次n^2求矩阵b[1~id[x], x+1,n]的和
三：二中的b大小为n*n显然不行。考虑将b[i]改为一颗权值线段树（求一段值域内的元素个数），这样大小变为nlogn。
四：每一次删除一个点，会修改线段树b[id[x]~n]，用时过久。不放对所有权值线段树的同一个区间求前缀和（实例：主席树）查询变为作差；这时修改线段树b[id[x]~n]相当于是单点修改更新前缀和，考虑使用树状数组来完成。

就是树状数组套权值线段树了。

#include <bits/stdc++.h>
using namespace std;

const int n=1e6+10;

int n,m,tot;
long long ans;
int root[n],bit[n],id[n],a[n],f[n],g[n];

struct edge {
    int ls,rs,sum;
} t[n*30];

void update(int&x,int l,int r,int w) {
    if(!x) x=++tot;
    t[x].sum+=(w!=0);
    if(l==r) return;
    int mid=(l+r)>>1;
    if(w<=mid) update(t[x].ls,l,mid,w);
    else update(t[x].rs,mid+1,r,w);
}
int l[n],cntl,r[n],cntr;
int f1(int x,int y,int w) {
    cntl=cntr=0, x--;
    for(; x>0; x-=(x&-x)) l[++cntl]=root[x];
    for(; y>0; y-=(y&-y)) r[++cntr]=root[y];
    int l=1, r=n, ret=0;
    while(l!=r) {
        int mid=(l+r)>>1;
        if(w<=mid) { //右区间全满
            for(int i=1; i<=cntl; ++i) ret-=t[t[l[i]].rs].sum;
            for(int i=1; i<=cntr; ++i) ret+=t[t[r[i]].rs].sum;
            for(int i=1; i<=cntl; ++i) l[i]=t[l[i]].ls;
            for(int i=1; i<=cntr; ++i) r[i]=t[r[i]].ls;
            r=mid;
        } else {
            for(int i=1; i<=cntl; ++i) l[i]=t[l[i]].rs;
            for(int i=1; i<=cntr; ++i) r[i]=t[r[i]].rs;
            l=mid+1;
        }
    }
    return ret;
}
int g1(int x,int y,int w) {
    cntl=cntr=0, x--;
    for(; x>0; x-=(x&-x)) l[++cntl]=root[x];
    for(; y>0; y-=(y&-y)) r[++cntr]=root[y];
    int l=1, r=n, ret=0;
    while(l!=r) {
        int mid=(l+r)>>1;
        if(mid<w) { //左区间全满
            for(int i=1; i<=cntl; ++i) ret-=t[t[l[i]].ls].sum;
            for(int i=1; i<=cntr; ++i) ret+=t[t[r[i]].ls].sum;
            for(int i=1; i<=cntl; ++i) l[i]=t[l[i]].rs;
            for(int i=1; i<=cntr; ++i) r[i]=t[r[i]].rs;
            l=mid+1;
        } else {
            for(int i=1; i<=cntl; ++i) l[i]=t[l[i]].ls;
            for(int i=1; i<=cntr; ++i) r[i]=t[r[i]].ls;
            r=mid;
        }
    }
    return ret;
}
int sum(int x,int y=0) {
    for(; x>0; x-=(x&-x)) y+=bit[x];
    return y;
}
void add(int x,int y) {
    for(; x<=n; x+=(x&-x)) bit[x]+=y;
} 

int main() {
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; ++i) {
        scanf("%d",&a[i]);
        id[a[i]]=i;
        f[i]=sum(n)-sum(a[i]);
        add(a[i],1);
        ans+=f[i];
    }
    for(int i=1; i<=n; ++i) bit[i]=0;
    for(int i=n; i>=1; --i) {
        g[i]=sum(a[i]);
        add(a[i],1);
    }
    update(root[0],1,n,0);
    for(int x; m--; ) {
        scanf("%d",&x);
        printf("%lld\n",ans);
        ans-=f[id[x]]-f1(1,id[x],x)+g[id[x]]-g1(id[x],n,x);
        for(int i=id[x]; i<=n; i+=(i&-i)) {
            update(root[i],1,n,x);
        }
    }
    return 0;
}