分块，错在10-15测试点有重复部分，求调。

#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10, W = 2200, C = 230;
int n, Q, c, l, r, lc, rc;
int a[N];
long long cnt = 0, cnt2 = 0;
int tr[2 * N]; 
vector<int> s[C], v;
bool a1, a2;
int lowbit(int x){return x & -x;}
void input(){
	cin>> n;
	c = n / W + 1; 
	for(int i = 1; i <= n; ++i) cin>> a[i], v.push_back(a[i]);
	sort(v.begin(), v.end());
	v.erase(unique(v.begin(), v.end()), v.end());
	for(int i = 1; i <= n; ++i) a[i] = lower_bound(v.begin(), v.end(), a[i]) - v.begin() + 1; 
	for(int i = 1; i <= n; ++i) s[(i - 1) / W + 1].push_back(a[i]);
	for(int i = 1; i <= c; ++i) sort(s[i].begin(), s[i].end());
	cin>>Q;
}
int count(int v, int nc){
	int ans = 0;
	for(int i = 1; i < nc; ++i){
		auto w = upper_bound(s[i].begin(), s[i].end(), v);
		ans += s[i].end() - w;
	}
	for(int i = nc + 1; i <= c; ++i){
		auto w = lower_bound(s[i].begin(), s[i].end(), v);
		ans += w - s[i].begin();
	}
	int flag = 0;
	
	for(int i = (nc - 1) * W + 1; i <= min(nc * W, n); ++i){
		if(a[i] == v) flag = 1;
		if(flag == 0){
			ans += a[i] > v; 
		}else if(flag == 1){
			ans += a[i] < v;
		}
	} 
	return ans;
}
void del(int v, int nc){
	auto w = lower_bound(s[nc].begin(), s[nc].end(), v);
	s[nc].erase(w);
}
void ins(int v, int nc){
	auto w = upper_bound(s[nc].begin(), s[nc].end(), v);
	s[nc].insert(w, v);
}
void add(int v){
	while(v <= n){
		++tr[v];
		v += lowbit(v);
	}
}
int query(int v){
	long long ans = 0;
	while(v > 0){
		ans += tr[v];
		v -= lowbit(v);
	}
	return ans;
}
void pre(){
	for(int i = 1; i <= n; ++i){
		cnt += query(n) - query(a[i]);
		add(a[i]);
	}
	for(int i = 1; i <= n; ++i){
		cnt2 += abs(a[i] - i);
	}
}
void op(){
	cout<<cnt<<'\n';
	for(int i = 1; i <= Q; ++i){
		cin >> l >> r;
		if(l > r) swap(l, r);
		lc = (l - 1) / W + 1, rc = (r - 1) / W + 1;
		cnt -= count(a[l], lc);
		cnt -= count(a[r], rc);
		if(a[l] > a[r]) cnt++; 
		del(a[l], lc);del(a[r], rc);
		ins(a[l], rc);ins(a[r], lc);
		swap(a[l], a[r]);
		cnt += count(a[l], lc);
		cnt += count(a[r], rc);
		if(a[l] > a[r]) cnt--; 
		cout<<cnt <<'\n';
	} 
}
int main(){
	cin.tie(0)->sync_with_stdio(false);
	input();
	pre();
	op();
}