块套树为什么会这么快。。
先跑出原序列逆序对。
显然交换两个位置$l,r$，对$[1,l)，(r,n]$里的数没有影响，所以只需要考虑$[l,r]$内的数。
设$(l,r)$内的数$a_i$，则按以下规则更新答案：
若$a_i<a_l$，则$ans--$
若$a_i>a_l$，则$ans++$
若$a_i<a_r$，则$ans++$
若$a_i>a_r$，则$ans--$
若$a_l<a_r$，则$ans++$
若$a_l>a_r$，则$ans--$
对每一个块建一个树状数组，查询的时候块内用树状数组查，块外暴力就好了。。。
#include<iostream> #include<cstring> #include<cstdlib> #include<cstdio> #include<algorithm> #include<cmath> using namespace std; const int maxn=20010; int n, m, blo, N, ans, l, r, L, R; int tree[150][maxn], bl[maxn], a[maxn], b[maxn], pretree[maxn]; inline void read(int &k) { int f=1; k=0; char c=getchar(); while(c<'0' || c>'9') c=='-' && (f=-1), c=getchar(); while(c<='9' && c>='0') k=k*10+c-'0', c=getchar(); k*=f; } inline void update(int ty, int x, int delta){for(;x<=N;x+=x&-x) tree[ty][x]+=delta;} inline int query(int ty, int x){int sum=0; for(;x;x-=x&-x) sum+=tree[ty][x]; return sum;} inline int min(int a, int b){return a<b?a:b;} int main() { read(n); blo=sqrt(n); for(int i=1;i<=n;i++) bl[i]=(i-1)/blo+1; for(int i=1;i<=n;i++) read(a[i]), b[i]=a[i]; N=n; sort(b+1, b+1+n); N=unique(b+1, b+1+N)-b-1; for(int i=1;i<=n;i++) a[i]=lower_bound(b+1, b+1+N, a[i])-b; for(int i=n;i;i--) ans+=query(0, a[i]-1), update(0, a[i], 1); printf("%d ", ans); for(int i=1;i<=n;i++) update(bl[i], a[i], 1); read(m); for(int i=1;i<=m;i++) { read(l); read(r); if(l>r) swap(l, r); int L=l+1, R=r-1; if(L<=R) { for(int j=L;j<=min(R, bl[L]*blo);j++) ans+=(a[j]>a[l]), ans-=(a[j]<a[l]), ans+=(a[j]<a[r]), ans-=(a[j]>a[r]); if(bl[L]!=bl[R]) for(int j=(bl[R]-1)*blo+1;j<=R;j++) ans+=(a[j]>a[l]), ans-=(a[j]<a[l]), ans+=(a[j]<a[r]), ans-=(a[j]>a[r]); for(int j=bl[L]+1;j<bl[R];j++) ans-=query(j, a[l]-1), ans+=query(j, N)-query(j, a[l]), ans-=query(j, N)-query(j, a[r]), ans+=query(j, a[r]-1); } if(a[l]<a[r]) ans++; else if(a[l]>a[r]) ans--; if(bl[l]!=bl[r]) update(bl[l], a[l], -1), update(bl[l], a[r], 1), update(bl[r], a[r], -1), update(bl[r], a[l], 1); swap(a[l], a[r]); printf("%d ", ans); } }