解法很多的题，可以块套树状数组，可以线段树套平衡树。我用的是树状数组套主席树。
题意:给出一段数列，m次操作，每次操作是交换两个位置的数，求每次操作后的逆序对数。(n,m<=2e4).
对于没有交换操作的逆序对数，可以直接用树状数组直接统计。
考虑每次交换操作(l,r),那么逆序对数会有什么变化呢。
1.如果a[l]>a[r],ans--,如果a[l]<a[r],那么ans++.
2.剩下的就是a[l]和a[r]对区间[l+1,r-1]之内数字的影响了。
ans+=([l+1,r-1]内比a[l]大的数)-([l+1,r-1]内比a[l]小的数)+([l+1,r-1]内比a[r]小的数)-([l+1,r-1]内比a[r]大的数)。
查询区间内比指定数字小或者大的数字数目，可以用主席树来实现。
现在要求支持动态交换两个数，显然用树状数组套主席树可以实现。
时间复杂度O(mlognlogn).常数略大。
# include <cstdio>
# include <cstring>
# include <cstdlib>
# include <iostream>
# include <vector>
# include <queue>
# include <stack>
# include <map>
# include <bitset>
# include <set>
# include <cmath>
# include <algorithm>
using namespace std;
# define lowbit(x) ((x)&(-x))
# define pi acos(-1.0)
# define eps 1e-
# define MOD
# define INF
# define mem(a,b) memset(a,b,sizeof(a))
# define FOR(i,a,n) for(int i=a; i<=n; ++i)
# define FO(i,a,n) for(int i=a; i<n; ++i)
# define bug puts("H");
# define lch p<<,l,mid
# define rch p<<|,mid+,r
# define mp make_pair
# define pb push_back
typedef pair<int,int> PII;
typedef vector<int> VI;
# pragma comment(linker, "/STACK:1024000000,1024000000")
typedef long long LL;
int Scan() {
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
const int N=;
//Code begin... int a[N], tree[N], ans;
int root[N], s[N*], ls[N*], rs[N*], sz, siz;
VI v; void add(int x){while (x<N) ++tree[x], x+=lowbit(x);}
int sum(int x){
int res=;
while (x) res+=tree[x], x-=lowbit(x);
return res;
}
void Update(int l, int r, int x, int &y, int L, int val){
y=++sz; s[y]=s[x]+val;
if (l==r) return ;
ls[y]=ls[x]; rs[y]=rs[x];
int mid=(l+r)>>;
if (L<=mid) Update(l,mid,ls[x],ls[y],L,val);
else Update(mid+,r,rs[x],rs[y],L,val);
}
int Query(int l, int r, int x, int L){
if (r<L) return ;
if (l>=L) return s[x];
int mid=(l+r)>>;
return Query(l,mid,ls[x],L)+Query(mid+,r,rs[x],L);
}
int Query2(int l, int r, int x, int L){
if (l>L) return ;
if (r<=L) return s[x];
int mid=(l+r)>>;
return Query2(l,mid,ls[x],L)+Query2(mid+,r,rs[x],L);
}
int Sum(int l, int x){
int res=;
while (l) res+=Query(,siz,root[l],x+), l-=lowbit(l);
return res;
}
int Sum2(int l, int x){
int res=;
while (l) res+=Query2(,siz,root[l],x-), l-=lowbit(l);
return res;
}
void Add(int x, int n, int l, int val){while (x<=n) Update(,siz,root[x],root[x],l,val), x+=lowbit(x);}
int main ()
{
int n, m, x, y;
scanf("%d",&n);
FOR(i,,n) scanf("%d",a+i), v.pb(a[i]);
sort(v.begin(),v.end());
siz=unique(v.begin(),v.end())-v.begin();
FOR(i,,n) {
a[i]=lower_bound(v.begin(),v.begin()+siz,a[i])-v.begin()+;
ans+=(i--sum(a[i])); add(a[i]);
Add(i,n,a[i],);
}
printf("%d\n",ans);
scanf("%d",&m);
while (m--) {
scanf("%d%d",&x,&y);
if (x>y) swap(x,y);
if (a[x]<a[y]) ++ans;
else if (a[x]>a[y]) --ans;
ans+=(Sum(y-,a[x])-Sum(x,a[x]))-(Sum(y-,a[y])-Sum(x,a[y]))+(Sum2(y-,a[y])-Sum2(x,a[y]))-(Sum2(y-,a[x])-Sum2(x,a[x]));
Add(x,n,a[x],-); Add(x,n,a[y],); Add(y,n,a[y],-); Add(y,n,a[x],);
swap(a[x],a[y]);
printf("%d\n",ans);
}
return ;
}