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;
}