BOJ)3770 대한민국

문제:icpc.me/3770

동해안과 서해안을 잇는 고속도로의 셋이 주어질 때 교차점의 수를 구하는 문제이다.

모든 고속도로를 받아서 동해안의 순서로 오름차순 정렬을 해준 뒤 동해안의 순서로 보면서 현재 보고 있는 고속도로보다 전에 봤던 고속도로 중 현재 고속도로보다 서해안이 큰 고속도로들의 수를 구해주면 된다.

이를 효과적으로 계산하기 위하여 세그먼트 트리를 사용해주면 된다.

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
int t, n, m, k, x, y, seg[10000];
long long r;
int update(int pos, int node, int x, int y) {
    if (y < pos || pos < x)return seg[node];
    if (x == y)return ++seg[node];
    int mid = (x + y) >> 1;
    return seg[node] = update(pos, node * 2, x, mid) + update(pos, node * 2 + 1, mid + 1, y);
}
int query(int lo, int hi, int node, int x, int y) {
    if (y < lo || hi < x)return 0;
    if (lo <= x&&y <= hi)return seg[node];
    int mid = (x + y) >> 1;
    return query(lo, hi, node * 2, x, mid) + query(lo, hi, node * 2 + 1, mid + 1, y);
}
int main() {
    scanf("%d", &t);
    for (int cnt = 1; cnt <= t; cnt++) {
        r = 0LL;
        memset(seg, 0, sizeof(seg));
        scanf("%d%d%d", &n, &m, &k);
        vector<pair<int, int>> vt;
        for (int i = 0; i < k; i++) {
            scanf("%d%d", &x, &y);
            vt.push_back({ x,y });
        }
        sort(vt.begin(), vt.end());
        for (int i = 0; i < vt.size(); i++) {
            int h = vt[i].first;
            r += (long long)query(vt[i].second + 1, max(m, n) + 1, 1, 1, max(m, n) + 1);
            update(vt[i].second, 1, 1, max(m, n) + 1);
        }
        printf("Test case %d: %lld\n", cnt, r);
    }
    return 0;
}