[bzoj3295][Cqoi2011][动态逆序对] (树套树)

Description

对于序列A，它的逆序对数定义为满足i<j，且A_i>A_j的数对(i,j)的个数。给1到n的一个排列，按照某种顺序依次删除m个元素，你的任务是在每次删除一个元素之前统计整个序列的逆序对数。

Input

输入第一行包含两个整数n和m，即初始元素的个数和删除的元素个数。以下n行每行包含一个1到n之间的正整数，即初始排列。以下m行每行一个正整数，依次为每次删除的元素。

Output

输出包含m行，依次为删除每个元素之前，逆序对的个数。

Sample Input

Sample Output

样例解释
(1,5,3,4,2)(1,3,4,2)(3,4,2)(3,2)(3)。

HINT

N<=100000 M<=50000

Solution

1.动态主席树（树状数组套主席树）

可以很简单地得出每个点的贡献，考虑怎样不重复计算就行了。去重用动态主席树实现

#include<stdio.h>
#include<string.h>
#define LL long long
#define RG register
#define inline __inline__ __attribute__((always_inline))
#define lbt(x) ((x)&(-x))
#define mid ((x>>1)+(y>>1)+(x&y&1))
#define N 100010
namespace BIT{
    int c[N];
    inline void clr(){
        memset(c,0,sizeof(c));
    }
    inline void add(RG int x,RG int n){
        for(;x<=n;x+=lbt(x))
            c[x]++;
    }
    inline int sum(RG int x){
        RG int res=0;
        for(;x;x-=lbt(x))
            res+=c[x];
        return res;
    }
}
LL ans;
int n,m,num[N],pos[N],left[N],right[N];
namespace FST{
    int sum[N<<6],ls[N<<6],rs[N<<6],rt[N],top,f[50],g[50];
    void modify(int &pr,RG int x,RG int y,RG int pos){
        if(!pr)pr=++top;
        sum[pr]++;
        if(x<y)
            pos<=mid?modify(ls[pr],x,mid,pos):
                modify(rs[pr],mid+1,y,pos);
    }
    inline void Back_d(RG int x,RG int y){
        f[0]=g[0]=0;
        for(;x;x-=lbt(x))
            f[++f[0]]=rt[x];
        for(;y;y-=lbt(y))
            g[++g[0]]=rt[y];
    }
    int Query_l(RG int x,RG int y,RG int pos){
        if(x==y)return 0;
        if(pos<=mid){
            RG int tmp=0;
            for(RG int i=1;i<=f[0];i++)
                tmp-=sum[rs[f[i]]],
                f[i]=ls[f[i]];
            for(RG int i=1;i<=g[0];i++)
                tmp+=sum[rs[g[i]]],
                g[i]=ls[g[i]];
            return tmp+Query_l(x,mid,pos);
        }
        for(RG int i=1;i<=f[0];i++)
            f[i]=rs[f[i]];
        for(RG int i=1;i<=g[0];i++)
            g[i]=rs[g[i]];
        return Query_l(mid+1,y,pos);
    }
    int Query_r(RG int x,RG int y,RG int pos){
        if(x==y)return 0;
        if(pos<=mid){
            for(RG int i=1;i<=f[0];i++)
                f[i]=ls[f[i]];
            for(RG int i=1;i<=g[0];i++)
                g[i]=ls[g[i]];
            return Query_r(x,mid,pos);
        }
        RG int tmp=0;
        for(RG int i=1;i<=f[0];i++)
            tmp-=sum[ls[f[i]]],
            f[i]=rs[f[i]];
        for(RG int i=1;i<=g[0];i++)
            tmp+=sum[ls[g[i]]],
            g[i]=rs[g[i]];
        return tmp+Query_r(mid+1,y,pos);
    }
    void main(RG int p){
        ans-=left[p]+right[p];
        Back_d(0,p-1);
        ans+=Query_l(1,n,num[p]);
        Back_d(p,n);
        ans+=Query_r(1,n,num[p]);
        for(RG int i=p;i<=n;i+=lbt(i))
            modify(rt[i],1,n,num[p]);
    }
}
int main(){
    scanf("%d%d",&n,&m);
    BIT::clr();
    for(RG int i=1;i<=n;i++){
        scanf("%d",&num[i]);
        pos[num[i]]=i;
        left[i]=i-1-BIT::sum(num[i]-1);
        ans+=left[i];
        BIT::add(num[i],n);
    }
    BIT::clr();
    for(RG int i=n;i;i--){
        right[i]=BIT::sum(num[i]-1);
        BIT::add(num[i],n);
    }
    while(m--){
        RG int x;
        scanf("%d",&x);
        printf("%lld
",ans);
        FST::main(pos[x]);
    }
    return 0;
}