就是很普通的分块的做法，求一段区间内大于或小于 $Key$ 的数量，复杂度应该是 $O(m\times\sqrt{n}\times log_n)$ 的吧，其中 $log$ 来自每次询问都需要的二分。

感觉这个复杂度完全没问题呀！但是却全 T 了啊，还有几个 MLE ，棒棒蒟蒻吧！

提交记录

#include<bits/stdc++.h>
#pragma GCC optimize(2)
#define lowbit( i ) ( i & ( -i ) )
using namespace std ;
const int Max = 2e4 + 10 , Nax = 150 ; 
// 输入
int A[Max] ;
int n , q ;
int a , b ; 
int Ans ; 
// 离散化
map < int , int > Q ;
int Sait[Max] ; 
//树状数组 
int f[Max] ;
void Fix( int a , int k ) {
	for(int i = a ; i <= n ; i += lowbit( i ) ) f[i] += k ; 
}
int Suber( int a ) {
	int Sum = 0 ;
	for(int i = a ; i ; i -= lowbit( i ) ) Sum += f[i] ; 
	return Sum ; 
}
//分块
int Begin[Nax] , End[Nax] ;  
int id[Max] ; 
int len , m ; 
int B[Max] ; 
bool Fil( int i , int Key , bool Falg ) {
	if( Falg ) {
		if( A[i] > Key ) Ans -- ; 
		if( A[i] < Key ) Ans ++ ; 
	} else {
		if( A[i] > Key ) Ans ++ ; 
		if( A[i] < Key ) Ans -- ; 
	}
}
int Fin( int l , int r , int Key , int Falg ) {
	// 0 : < Key 的最大下标
	// 1 : > Key 的最小下标
	while( l < r ) {
		int mid = l + r >> 1 ;  
		if( Falg ) {
			if( B[mid] > Key ) r = mid ; 
			else l = mid + 1 ; 
		} else {
			mid ++ ; 
			if( B[mid] < Key ) l = mid ;
			else r = mid - 1 ; 
		}
	}
	if( Falg && B[l] <= Key ) {
		l ++ ; 
	} 
	if( !Falg && B[l] >= Key ){
		l -- ; 
	}
	return l ;
}
void Nul( int l , int r , int Key , bool Falg ) {
	// 查询 l ~ r 中有多少比 Key 大 ， 比 Key 小
	if( id[r] - id[l] <= 1 ) {
		for(int i = l ; i <= r ; i ++ ) {
			Fil( i , Key , Falg ) ; 
		}
	} else {
		for(int i = l ; i <= End[id[l]] ; i ++ ) {
			Fil( i , Key , Falg ) ; 
		}
		for(int i = Begin[id[r]] ; i <= r ; i ++ ) {
			Fil( i , Key , Falg ) ; 
		} 
		for(int i = id[l] + 1 ; i <= id[r] - 1 ; i ++ ) {
			if( Falg ) {
				Ans -= End[i] - Fin( Begin[i] , End[i] , Key , 1 ) + 1 ; 
				Ans += Fin( Begin[i] , End[i] , Key , 0 ) - Begin[i] + 1 ; 
			} else {
				Ans += End[i] - Fin( Begin[i] , End[i] , Key , 1 ) + 1 ; 
				Ans -= Fin( Begin[i] , End[i] , Key , 0 ) - Begin[i] + 1 ; 
			}
		}
	}
}
void Sort( int Key ) {
	for(int i = Begin[id[Key]] ; i <= End[id[Key]] - 1 ; i ++ ) {
		if( B[i] > B[i + 1] ) swap( B[i] , B[i + 1] ) ;
	}
	for(int i = End[id[Key]] ; i <= Begin[id[Key]] + 1 ; i ++ ) {
		if( B[i] < B[i - 1] ) swap( B[i] , B[i + 1] ) ;
	}
}
int main( ) {
//	freopen("1.in" , "r" , stdin ) ; 
	scanf("%d" , &n ) ; 
	len = sqrt( n ) ;
	if( n % len == 0 ) m = n / len ;
	else m = n / len + 1 ; 
	for(int i = 1 ; i <= n ; i ++ ) {
		id[i] = ( i - 1 ) / len + 1 ; 
		scanf("%d" , &A[i] ) ;
		Sait[i] = A[i] ;
	} 
	// 分块
	for(int i = 1 ; i <= m ; i ++ ) {
		Begin[i] = ( i - 1 ) * len + 1 ; 
		End[i] = min( i * len , n ) ;  
	}
	// 离散化
	sort( Sait + 1 , Sait + n + 1 ) ; 
	for(int i = 1 , Val = 0 ; i <= n ; i ++ ) {
		if( Sait[i] != Sait[i - 1] ) Q[Sait[i]] = ++ Val ;
	}
	for(int i = 1 ; i <= n ; i ++ ) B[i] = A[i] = Q[A[i]] ; 
	for(int i = 1 ; i <= m ; i ++ ) {
		sort( B + Begin[i] , B + End[i] + 1 ) ; 
	}
	// 树状数组求逆序对
	for(int i = 1 ; i <= n ; i ++ ) {
		Ans += Suber( n ) - Suber( A[i] ) ; 
		Fix( A[i] , 1 ) ; 
	}
	printf("%d\n" , Ans ) ;
	scanf("%d" , &q ) ; 
	while( q -- ) {
		scanf("%d%d" , &a , &b ) ;
		if( a > b ) swap( a , b ) ; 
		Nul( a + 1 , b - 1 , A[a] , 0 ) ; 
		Nul( a + 1 , b - 1 , A[b] , 1 ) ; 
		if( A[a] > A[b] ) Ans -- ; 
		else Ans ++ ; 
		printf("%d\n" , Ans ) ;
		B[Fin( Begin[id[a]] , End[id[a]] , A[a] , 1 ) - 1] = A[b] ;
		B[Fin( Begin[id[b]] , End[id[b]] , A[b] , 1 ) - 1] = A[a] ;
		Sort( a ) ; 
		Sort( b ) ; 
		swap( A[a] , A[b] ) ;
	}
	return false ; 
}