BZOJ2141 排队

题目传送门

Solution:

这就是一个裸的动态逆序对问题,对于每一次交换,可以看作是先删掉一个数,再删一个数,然后加入一个数,再加入一个数,所以只要解决插入和删除就可以了。对于删除,我们只需要知道在x前面有几个数比它大,在它后面有几个数比它小。对于插入,我们也只需要知道在x前面有几个数比它大,在它后面有几个数比它小。然后就可以维护逆序对的数量了。这个可以用树套树来完成,外层树状数组表示位置为1~i的前缀和,内层线段树表示权值在l~r的数的个数。

code:

#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cmath>
using namespace std;
int num,b[100005],a[100005],n,m,bit[100005],lson[10000005],rson[10000005],tree[10000005],cnt,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;
}
void del(int x){
    ans-=queryx(x-1,a[x]+1,n);
    ans-=queryx(n,1,a[x]-1);
    ans+=queryx(x-1,1,a[x]-1);
    addx(x,a[x],-1);
}
void ins(int x){
    ans+=queryx(x-1,a[x]+1,n);
    ans+=queryx(n,1,a[x]-1);
    ans-=queryx(x-1,1,a[x]-1);
    addx(x,a[x],1);
}
int main(){
    scanf("%d",&n);
    cnt=n;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        b[i]=a[i];
    }
    num=n;
    sort(b+1,b+1+num);
    num=unique(b+1,b+1+num)-b-1;
    for(int i=1;i<=n;i++){
        a[i]=lower_bound(b+1,b+1+num,a[i])-b;
        ans+=queryx(i-1,a[i]+1,n);
        addx(i,a[i],1);
    }
    printf("%d\n",ans);
    scanf("%d",&m);
    while(m--){ 
        int x,y;
        scanf("%d%d",&x,&y);
        del(x); 
        del(y);
        swap(a[x],a[y]);
        ins(x);
        ins(y);
        printf("%d\n",ans);
    }
    return 0;
}

2 thoughts on “BZOJ2141 排队”

  1. I precisely wanted to appreciate you all over again. I am not sure what I would have carried out without these ideas revealed by you about such a subject matter. It had become a real scary dilemma in my view, however , considering a new specialized technique you solved it made me to weep for gladness. I’m happier for your assistance and have high hopes you know what an amazing job that you are carrying out training some other people all through your blog. Probably you’ve never encountered all of us.

Leave a Comment

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