BZOJ3295 动态逆序对(树套树)

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3295

对于每一次修改,我们只需要知道在x前面有几个数比它大,在它后面有几个数比它小,然后就可以维护逆序对的数量了。那么问题是怎么算出在x前面有几个比它小呢?可以用树套树,外层树状数组,内层线段树。外层树状数组维护位置为1~i的前缀和,内层线段树维护值在l~r的数有几个。然后就可以完美的解决问题了。这道题用bit套线段树代码非常短。

code:

#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cmath>
using namespace std;
int a[100005],n,m,id[100005],bit[100005],lson[10000005],rson[10000005],tree[10000005],cnt;
long long ans;
int lowbit(int x){
    return x&-x;
}
void addy(int &u,int l,int r,int x,int y){
    if(!u)
        u=++cnt;
    if(l==r){
        tree[u]+=y;
        return;
    }
    int mid=(l+r)>>1;
    if(x<=mid)
        addy(lson[u],l,mid,x,y);
    else
        addy(rson[u],mid+1,r,x,y);
    tree[u]=tree[lson[u]]+tree[rson[u]];
}
void addx(int x,int y,int val){
    while(x<=n){
        addy(x,1,n,y,val);
        x+=lowbit(x);
    }
}
int queryy(int u,int l,int r,int i,int j){
    if(!u)
        return 0;
    if(l==i&&r==j)
        return tree[u];
    int mid=(l+r)>>1;
    if(j<=mid)
        return queryy(lson[u],l,mid,i,j);
    else
    if(i>mid)
        return queryy(rson[u],mid+1,r,i,j);
    return queryy(lson[u],l,mid,i,mid)+queryy(rson[u],mid+1,r,mid+1,j);
}
int queryx(int x,int l,int r){
    int ans=0;
    while(x){
        ans+=queryy(x,1,n,l,r);
        x-=lowbit(x);
    }
    return ans;
}
int main(){
    scanf("%d%d",&n,&m);
    cnt=n;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        ans+=(long long)queryx(i-1,a[i]+1,n);
        id[a[i]]=i;
        addx(i,a[i],1);
    }
    while(m--){
        printf("%lld\n",ans);
        int x;
        scanf("%d",&x);
        ans-=(long long)queryx(id[x]-1,x+1,n);
        ans-=(long long)queryx(n,1,x-1);
        ans+=(long long)queryx(id[x]-1,1,x-1);
        addx(id[x],x,-1);
    }
    return 0;
}

1 thought on “BZOJ3295 动态逆序对(树套树)”

  1. I not to mention my guys have been checking out the great information on your website and immediately got an awful suspicion I never expressed respect to you for those tips. All of the guys came absolutely passionate to learn them and have in effect actually been making the most of those things. Appreciate your genuinely very accommodating as well as for settling on this kind of marvelous areas millions of individuals are really desirous to understand about. My personal honest apologies for not expressing appreciation to you earlier.

Leave a Comment

电子邮件地址不会被公开。 必填项已用*标注