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;
}

Leave a Comment

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