喜闻乐见的乱搞解法！首先要 $O(n\log n)$ 预处理逆序对数（这里使用的是树状数组），然后对于每一次修改，$O(n)$ 地计算贡献。就这样，我们得到了一份 $O(n \log n+nm)$ 的代码！

#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=500001;
inline int lowbit(int x){
	return x&(-x);
}
int n,c[maxn],m;
pair<int,int> a[maxn];
void upd(int id){
	while(id<=n){
		++c[id];
		id+=lowbit(id);
	}
}
long long query(int id){
	long long sum=0;
	while(id){
		sum+=c[id];
		id-=lowbit(id);
	}
	return sum;
}
int main(){
	cin >> n;
	long long ans=0;
	for(int i=1;i<=n;i++){
		cin >> a[i].first;
		a[i].second=i;
	}
	sort(a+1,a+n+1);
	for(int i=n;i>=1;i--){
		upd(a[i].second);
		ans+=query(a[i].second-1);
	}
	sort(a+1,a+n+1,[](const pair<int,int> &x,const pair<int,int> &y){return x.second<y.second;});
	cout << ans << endl; 
	cin >> m;
	while(m--){
		int p,q;
		cin >> p >> q;
		if(p>q)	swap(p,q);
		for(int i=p;i<q;i++){
			ans+=a[i].first>a[p].first;
			ans-=a[i].first>a[q].first;
			ans+=(a[q].first>a[i].first)-(a[p].first>a[i].first);
		}
		swap(a[p].first,a[q].first);
		cout << ans<< endl;
	}
	return 0;
}