C++ 解法, 执行用时: 87ms, 内存消耗: 22652K, 提交时间: 2021-10-26 13:09:54

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int a[20010],lsh[20010];
int t,n;
ll tree[200][20010];

inline int lowbit(int x){
	return x&(-x);
}

void add(int x,int y,int k){
	for(int i=y;i<=n;i+=lowbit(i)) tree[x][i]+=k;
}

ll find(int x,int y){
	ll ans=0;
	for(int i=y;i>0;i-=lowbit(i)) ans+=tree[x][i];
	return ans;
}

int main()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int m;
	cin>>n;
	t=sqrt(n);
	for(int i=1;i<=n;i++){
		cin>>a[i]; lsh[i]=a[i];
	}
	sort(lsh+1,lsh+n+1);
	int cnt=unique(lsh+1,lsh+n+1)-lsh-1;
	for(int i=1;i<=n;i++) a[i]=cnt-(lower_bound(lsh+1,lsh+cnt+1,a[i])-lsh)+1;
	
	ll ans=0;
	for(int i=1;i<=n;i++){
		for(int j=0;j<=i/t;j++) ans+=find(j,a[i]-1);
		add(i/t,a[i],1);
	}
	cout<<ans<<"\n";
	cin>>m;
	int x,y;
	while(m--){
		cin>>x>>y;
		if(x>y) swap(x,y);
		//cout<<x/t<<" "<<y/t<<"\n";
		if(x/t==y/t){
			for(int i=x+1;i<y;i++){
				if(a[i]>a[x]) ans--;
				if(a[i]<a[x]) ans++;
				if(a[i]>a[y]) ans++;
				if(a[i]<a[y]) ans--;
			}
		}
		else{
			//cout<<ans<<"\n";
			for(int i=x/t+1;i<y/t;i++){
				ans+=find(i,a[x]-1)-(t-find(i,a[x]))-find(i,a[y]-1)+(t-find(i,a[y]));
			}
			//cout<<ans<<'\n';
			for(int i=x+1;i<(x/t+1)*t;i++){
				if(a[i]>a[x]) ans--;
				if(a[i]<a[x]) ans++;
				if(a[i]>a[y]) ans++;
				if(a[i]<a[y]) ans--;
			}
			for(int i=y/t*t;i<y;i++){
				if(a[i]>a[x]) ans--;
				if(a[i]<a[x]) ans++;
				if(a[i]>a[y]) ans++;
				if(a[i]<a[y]) ans--;
		    }
		}
		if(a[x]>a[y]) ans++;
		if(a[x]<a[y]) ans--;
		add(x/t,a[x],-1); add(y/t,a[y],-1);
		swap(a[x],a[y]);
		add(x/t,a[x],1); add(y/t,a[y],1);
		cout<<ans<<'\n';
	}
	return 0;
}