rt

O2

不开O2

#include <bits/stdc++.h>

using namespace std;

const int N = 2e4 + 10, S = 250;

int b[S][S], a[N];
int n, m;

inline int query (int l, int r, int x) {
	if (l > r) return 0;
	int size = sqrt(n);
	int bl = (l - 1) / size, br = (r - 1) / size, res = 0;
	if (bl == br) {
		for (int i = l;i <= r;i++) if (a[i] < x) res++;
		return res;
	}
	for (int i = l;i <= (bl + 1) * size;i++) if (a[i] < x) res++;
	for (int i = br * size + 1;i <= r;i++) if (a[i] < x) res++;
	for (int i = bl + 1;i < br;i++) res += lower_bound(b[i], b[i] + size, x) - b[i];
	return res;
}

inline int query_ (int l, int r, int x) {
	if (l > r) return 0;
	int size = sqrt(n);
	int bl = (l - 1) / size, br = (r - 1) / size, res = 0;
	if (bl == br) {
		for (int i = l;i <= r;i++) if (a[i] <= x) res++;
		return res;
	}
	for (int i = l;i <= (bl + 1) * size;i++) if (a[i] <= x) res++;
	for (int i = br * size + 1;i <= r;i++) if (a[i] <= x) res++;
	for (int i = bl + 1;i < br;i++) res += upper_bound(b[i], b[i] + size, x) - b[i];
	return res;
}

inline void change (int idx, int x) {
	if (a[idx] == x) return;
	int size = sqrt(n);
	if (size >= 250) while(1);
	int old = a[idx], bi = (idx - 1) / size, pos = 0;
	a[idx] = x;
	while (b[bi][pos] < old) pos++;
	b[bi][pos] = x;
	if (x < old) while (pos > 0 && b[bi][pos - 1] > b[bi][pos]) {
		if (pos - 1 < 0) while (1);
		swap(b[bi][pos - 1], b[bi][pos]), pos--;
	}
	else while (pos < size - 1 && b[bi][pos + 1] < b[bi][pos]) {
		if (pos + 1 >= size) while (1);
		swap(b[bi][pos + 1], b[bi][pos]), pos++;
	}
}

int main () {
	scanf("%d", &n);
	int size = sqrt(n), ans = 0;
	for (int i = 1;i <= n;i++) scanf("%d", &a[i]), b[(i - 1) / size][(i - 1) % size] = a[i];
	for (int i = 1;i <= n;i++) for (int j = 1;j < i;j++) if (a[j] > a[i]) ans++;
	int mb = (n - 1) / size, ml = (n - 1) % size;
	for (int i = 0;i < mb;i++) sort(b[i], b[i] + size);
	sort(b[mb], b[mb] + ml);
	printf("%d\n", ans);
	scanf("%d", &m);
	while (m--) {
		int x, y;
		scanf("%d%d", &x, &y);
		if (x > y) swap(x, y);
		ans += query(x + 1, y - 1, a[y]); ans -= (y - x - 1) - query_(x + 1, y - 1, a[y]);
		ans -= query(x + 1, y - 1, a[x]); ans += (y - x - 1) - query_(x + 1, y - 1, a[x]);
		if (a[x] < a[y]) ans++;
		if (a[x] > a[y]) ans--;
		int ox = a[x], oy = a[y];
		change(x, oy); change(y, ox);
		printf("%d\n", ans);
	}
	return 0;
}