解法很多的题，可以块套树状数组，可以线段树套平衡树。我用的是树状数组套主席树。
题意:给出一段数列，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-8 # define MOD 30031 # define INF 1000000000 # 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<<1,l,mid # define rch p<<1|1,mid+1,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=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } const int N=20005; //Code begin... int a[N], tree[N], ans; int root[N], s[N*400], ls[N*400], rs[N*400], sz, siz; VI v; void add(int x){while (x<N) ++tree[x], x+=lowbit(x);} int sum(int x){ int res=0; 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)>>1; if (L<=mid) Update(l,mid,ls[x],ls[y],L,val); else Update(mid+1,r,rs[x],rs[y],L,val); } int Query(int l, int r, int x, int L){ if (r<L) return 0; if (l>=L) return s[x]; int mid=(l+r)>>1; return Query(l,mid,ls[x],L)+Query(mid+1,r,rs[x],L); } int Query2(int l, int r, int x, int L){ if (l>L) return 0; if (r<=L) return s[x]; int mid=(l+r)>>1; return Query2(l,mid,ls[x],L)+Query2(mid+1,r,rs[x],L); } int Sum(int l, int x){ int res=0; while (l) res+=Query(1,siz,root[l],x+1), l-=lowbit(l); return res; } int Sum2(int l, int x){ int res=0; while (l) res+=Query2(1,siz,root[l],x-1), l-=lowbit(l); return res; } void Add(int x, int n, int l, int val){while (x<=n) Update(1,siz,root[x],root[x],l,val), x+=lowbit(x);} int main () { int n, m, x, y; scanf("%d",&n); FOR(i,1,n) scanf("%d",a+i), v.pb(a[i]); sort(v.begin(),v.end()); siz=unique(v.begin(),v.end())-v.begin(); FOR(i,1,n) { a[i]=lower_bound(v.begin(),v.begin()+siz,a[i])-v.begin()+1; ans+=(i-1-sum(a[i])); add(a[i]); Add(i,n,a[i],1); } printf("%d ",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-1,a[x])-Sum(x,a[x]))-(Sum(y-1,a[y])-Sum(x,a[y]))+(Sum2(y-1,a[y])-Sum2(x,a[y]))-(Sum2(y-1,a[x])-Sum2(x,a[x])); Add(x,n,a[x],-1); Add(x,n,a[y],1); Add(y,n,a[y],-1); Add(y,n,a[x],1); swap(a[x],a[y]); printf("%d ",ans); } return 0; }