题解：SP4226 MSE06H - Japan

cyhyeee · 2025-01-22 15:02:39 · 题解

跟逆序对几乎一模一样。

这道题要考虑的只有 x1 \lt x2 \And y1 \gt y2 或 x1 \gt x2 \And y1 \lt y2，也就是二位偏序。所以先按 x 坐标排序，再做逆序对就行了。

AC CODE:

#include <bits/stdc++.h>
#define int long long
using namespace std;
void cmax(int &x, int y) {x = (x > y) ? x : y;}
void cmin(int &x, int y) {x = (x < y) ? x : y;}

int n, m, k, tot;
int tree[1000005];
struct ovo {
    int x, y;
}a[1000005];
int lowbit(int x) {
    return x & -x;
}
int getsum(int x) {
    int ans = 0;
    while (x > 0) {
        ans += tree[x];
        x -= lowbit(x);
    }
    return ans;
}
void add(int x, int k) {
    while (x <= m) {
        tree[x] += k;
        x += lowbit(x);
    }
}
bool cmp(ovo x, ovo y) {
    if (x.x == y.x) return x.y < y.y;
    return x.x < y.x;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T;
    cin >> T;
    for (int testID = 1; testID <= T; testID ++) {
        memset(a, 0, sizeof(a));
        memset(tree, 0, sizeof(tree));
        tot = 0;
        cin >> n >> m >> k;
        for (int i = 1; i <= k; i ++) {
            cin >> a[i].x >> a[i].y;
        }
        sort(a + 1, a + k + 1, cmp);
        for (int i = k; i >= 1; i --) {
            tot += getsum(a[i].y - 1);
            add(a[i].y, 1);
        }
        cout << "Test case " << testID << ": " << tot << '\n';
    }
    return 0;
}