# BZOJ2141 排队

### 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.