AC代码：交换后再跑一遍逆序对$O(nmlogn)$

#include<iostream>
#include<map>
#define MAXN 100010
#define INF 1000000000
#define LL long long
using namespace std;
int n;
map<int,int> mp;
int a[1000010];
int tr[1000010];
int now;
void add(int p){for (;p<=now;p+=p&(-p)) tr[p]++;}
int query(int p){int ans=0;for (;p;p-=p&(-p)) ans+=tr[p];return ans;}
void Main(){
	for (int i=1;i<=n;i++) tr[i]=0;
    LL ans=0;
    for (int i=1;i<=n;i++){
        ans+=i-1-query(a[i]);
        add(a[i]);
    }
    cout<<ans<<"\n";
}
int main(){
    std::ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
	cin>>n;
    for (int i=1;i<=n;i++) cin>>a[i],mp[a[i]]=1;
    for (auto& it:mp){
        it.second=++now;
    }
    for (int i=1;i<=n;i++) a[i]=mp[a[i]];
    Main();
	int q;cin>>q;
	while (q--){
		int x,y;cin>>x>>y;
		swap(a[x],a[y]);
		Main();
	}
}