P1975 [国家集训队] 排队-526互联

题意

给定序列，每次交换两个数。询问逆序对个数。

Sol

暴力草过去了。

分块的做法等会来补。

Code

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <array>
#define int long long
using namespace std;
#ifdef ONLINE_JUDGE

#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
char buf[1 << 23], *p1 = buf, *p2 = buf, ubuf[1 << 23], *u = ubuf;

#endif
int read() {
	int p = 0, flg = 1;
	char c = getchar();
	while (c < '0' || c > '9') {
		if (c == '-') flg = -1;
		c = getchar();
	}
	while (c >= '0' && c <= '9') {
		p = p * 10 + c - '0';
		c = getchar();
	}
	return p * flg;
}
void write(int x) {
	if (x < 0) {
		x = -x;
		putchar('-');
	}
	if (x > 9) {
		write(x / 10);
	}
	putchar(x % 10 + '0');
}

const int N = 2e4 + 5;

namespace Bit {

array <int, N> edge;

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

void modify(int x, int y, int n) {
	while (x <= n) {
		edge[x] += y;
		x += lowbit(x);
	}
	return;
}

int query(int x) {
	int ans = 0;
	while (x) {
		ans += edge[x];
		x -= lowbit(x);
	}
	return ans;
}

}

array <int, N> s, h;

signed main() {
	int n = read();
	for (int i = 1; i <= n; i++)
		s[i] = h[i] = read();
	sort(h.begin() + 1, h.begin() + 1 + n);
	int k = unique(h.begin() + 1, h.begin() + 1 + n) - h.begin() - 1;
	for (int i = 1; i <= n; i++)
		s[i] = lower_bound(h.begin() + 1, h.begin() + 1 + k, s[i]) - h.begin();
	int ans = 0;
	for (int i = n; i >= 1; i--) {
		ans += Bit::query(s[i] - 1);
		Bit::modify(s[i], 1, n);
	}
	write(ans), puts("");
	int q = read();
	while (q--) {
		int x = read(), y = read();
		if (x > y) swap(x, y);
		if (s[x] < s[y]) ans++;
		if (s[x] > s[y]) ans--;
		for (int i = x + 1; i < y; i++) {
			if (s[x] > s[i]) ans--;
			if (s[x] < s[i]) ans++;
			if (s[y] < s[i]) ans--;
			if (s[y] > s[i]) ans++;
		}
		write(ans), puts("");
		swap(s[x], s[y]);
	}
	return 0;
}