【bzoj2141】排队 [国家集训队2011]排队（树套树）

题目描述

排排坐，吃果果，生果甜嗦嗦，大家笑呵呵。你一个，我一个，大的分给你，小的留给我，吃完果果唱支歌，大家乐和和。

红星幼儿园的小朋友们排起了长长地队伍，准备吃果果。不过因为小朋友们的身高有所区别，排成的队伍高低错乱，极不美观。设第i个小朋友的身高为hi，我们定义一个序列的杂乱程度为：满足i<j且hi>hj的(i,j)数量。

幼儿园阿姨每次会选出两个小朋友，交换他们的位置，请你帮忙计算出每次交换后，序列的杂乱程度。为方便幼儿园阿姨统计，在未进行任何交换操作时，你也应该输出该序列的杂乱程度。

题解

　　新技能get

　　树状数组+动态开点线段树

　　具体看代码（因为我讲不来）

 //minamoto

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 using namespace std;

 const int N=;

 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)

 char buf[<<],*p1=buf,*p2=buf;

 inline int read(){

     #define num ch-'0'

     char ch;bool flag=;int res;

     while(!isdigit(ch=getc()))

     (ch=='-')&&(flag=true);

     for(res=num;isdigit(ch=getc());res=res*+num);

     (flag)&&(res=-res);

     #undef num

     return res;

 }

 char sr[<<],z[];int C=-,Z;

 inline void Ot(){fwrite(sr,,C+,stdout),C=-;}

 inline void print(int x){

     if(C><<)Ot();if(x<)sr[++C]=,x=-x;

     while(z[++Z]=x%+,x/=);

     while(sr[++C]=z[Z],--Z);sr[++C]='\n';

 }

 struct node{

     int v,id;

     inline bool operator <(const node &b)const{return v<b.v;}

 }a[N];

 int n,m,x,y,tot,ans,b[N],c[N];

 inline void add(int x){

     for(;x<=n;x+=x&-x) ++c[x];

 }

 inline int sum(int x){

     int res=;

     for(;x;x-=x&-x) res+=c[x];

     return res;

 }

 int cnt,rt[N],v[N*],L[N*],R[N*];

 void insert(int &u,int l,int r,int x,int k){

     if(!u) u=++cnt;v[u]+=k;

     if(l==r) return;int mid=l+r>>;

     if(x<=mid) insert(L[u],l,mid,x,k);

     else insert(R[u],mid+,r,x,k);

 }

 void push(int x,int y,int k){

     for(;x<=n;x+=x&-x) insert(rt[x],,n,y,k);

 }

 int Query(int u,int l,int r,int ql,int qr){

     if(!u) return ;

     if(ql<=l&&qr>=r) return v[u];

     int mid=l+r>>;

     int res=;

     if(ql<=mid) res+=Query(L[u],l,mid,ql,qr);

     if(qr>mid) res+=Query(R[u],mid+,r,ql,qr);

     return res;

 }

 int query(int l,int r,int ql,int qr){

     if(l>r||ql>qr) return ;

     int sum=;--l;

     for(;r;r-=r&-r) sum+=Query(rt[r],,n,ql,qr);

     for(;l;l-=l&-l) sum-=Query(rt[l],,n,ql,qr);

     return sum;

 }

 int main(){

     //freopen("testdata.in","r",stdin);

     n=read();

     for(int i=;i<=n;++i) a[i]=(node){read(),i};

     sort(a+,a++n);

     for(int i=;i<=n;++i){

         if(a[i].v!=a[i-].v) ++tot;

         b[a[i].id]=tot;

     }

     for(int i=n;i;--i) ans+=sum(b[i]-),add(b[i]);

     for(int i=;i<=n;++i) push(i,b[i],);

     m=read(),print(ans);

     while(m--){

         int x=read(),y=read();

         if(x>y) swap(x,y);

         ans+=query(x+,y-,,b[y]-);

         ans-=query(x+,y-,b[y]+,n);

         ans+=query(x+,y-,b[x]+,n);

         ans-=query(x+,y-,,b[x]-);

         if(b[x]>b[y]) --ans;

         if(b[x]<b[y]) ++ans;

         push(x,b[x],-),push(y,b[y],-);

         push(y,b[x],),push(x,b[y],);

         swap(b[x],b[y]);

         print(ans);

     }

     Ot();

     return ;

 }