0pts 求条

P2448 无尽的生命 - 洛谷

#include<bits/stdc++.h>
#define lowbit(x) x&(-(x))
#define int long long
using namespace std;
int t[1000005], n;
struct node {
	int a, b;
} a[1000005];
int v[1000005], w[1000005], cnt, k[1000005], ans, hs[1000005], ccnt, tt[1000005];
int fd(int x) {
	return lower_bound(v + 1, v + 2 * n + 1, x) - v;
}
void add(int x, int k) {
	for (int i = x; i <= n; i += lowbit(i)) {
		t[i] += k;
	}
}
int sum(int x) {
	int res = 0;
	for (int i = x; i >= 1; i -= lowbit(i)) {
		res += t[i];
	}
	return res;
}
signed main() {
	cin >> n;
	for (int i = 1; i <= 2 * n; i++) k[i] = i;
	for (int i = 1; i <= n; i++) {
		cin >> a[i].a >> a[i].b;
		v[++cnt] = a[i].a;
		w[cnt] = a[i].a;
		v[++cnt] = a[i].b;
		w[cnt] = a[i].b;
	}
	sort(v + 1, v + 2 * n + 1);
	int c = unique(v + 1, v + 2 * n + 1) - (v + 1);
	for (int i = 1; i <= 2 * n; i++) w[i] = lower_bound(v + 1, v + c + 1, w[i]) - v;
	for (int i = 1; i <= 2 * n; i += 2) {
		swap(k[w[i]], k[w[i + 1]]);
	}
	for (int i = 1; i <= 2 * n; i++) tt[i] = v[i];
	for (int i = 1; i <= n; i++) swap(tt[a[i].a], tt[a[i].b]);
	for (int i = 1; i <= 2 * n; i++) ans += abs(tt[i] - v[i]) - abs(fd(tt[i]) - (i + 1));
	for (int i = 2 * n; i >= 1; i--) {
		add(k[i], 1);
		ans += sum(k[i] - 1);
	}
	cout << ans;
	return 0;
}