题目链接：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 ;
}