首页 > 代码库 > [bzoj3295][Cqoi2011][动态逆序对] (树套树)

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

2024-09-01 00:53:03   216人阅读

Description

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

Input

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

Output

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

Sample Input

5 4153425142

 


Sample Output

5221

 


样例解释
(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 100010namespace 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\n",ans);        FST::main(pos[x]);    }    return 0;}

 

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


联系
我们