BZOJ2141: 排队

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=2141

分块加树状数组。

离散化之后，每一个块建一个树状数组。交换x，y，与x左边的数和y右边的数无关，只需处理>x，<y的数。

话说还可以用树套树来写，不过常数太大，比分块加树状数组慢。

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #include<cmath>

 #define inf 1<<30

 #define maxn 20005

 using namespace std;

 int n,m,nn,tot,ans,a[maxn],t[][maxn];

 struct fuck{int x,id;}c[maxn];

 int read(){

     int x=,f=; char ch;

     for(ch=getchar();ch<''||ch>'';ch=getchar()) if(ch=='-') f=-;

     for(;ch>=''&&ch<='';ch=getchar()) x=x*+ch-'';

     return x*f;

 }

 bool comp(fuck a,fuck b){return a.x<b.x;}

 int p(int x){return (x-)/nn+;}

 void change(int f,int x,int y){for(int i=x;i<=tot;i+=i&-i) t[f][i]+=y;}

 int query(int f,int x){int y=;for(int i=x;i;i-=i&-i) y+=t[f][i];return y;}

 int main(){

     n=read(); nn=sqrt(n);

     for(int i=;i<=n;i++) c[i].x=read(),c[i].id=i;

     sort(c+,c+n+,comp);

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

         if(c[i].x!=c[i-].x) ++tot;

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

     }

     for(int i=n;i;i--){

         ans+=query(,a[i]-);

         change(,a[i],);

     }

     printf("%d\n",ans);

     for(int i=;i<=n;i++) change(p(i),a[i],);

     m=read();

     int x,y;

     while(m--){

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

         for(int i=p(x)+;i<p(y);i++){

             ans-=query(i,a[x]-); ans+=query(i,tot)-query(i,a[x]);

             ans-=query(i,tot)-query(i,a[y]); ans+=query(i,a[y]-);

         }

         for(int i=x+;p(i)==p(x)&&i<y;i++){

             if(a[i]<a[x]) ans--; if(a[i]>a[x]) ans++;

             if(a[i]<a[y]) ans++; if(a[i]>a[y]) ans--;

         }

         if(p(x)!=p(y))

         for(int i=y-;p(i)==p(y);i--){

             if(a[i]<a[x]) ans--; if(a[i]>a[x]) ans++;

             if(a[i]<a[y]) ans++; if(a[i]>a[y]) ans--;

         }

         if(a[x]<a[y]) ans++; if(a[x]>a[y]) ans--;

         change(p(x),a[x],-); change(p(x),a[y],);

         change(p(y),a[y],-); change(p(y),a[x],);

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

         printf("%d\n",ans);

     }

     return ;

 }