3770 - 대한민국

https://www.acmicpc.net/problem/3770
http://www.spoj.com/problems/MSE06H/

세그먼트 트리로 풀었다.

위 그림을 참고해서 풀었음. 다듬어서 다시 업로드 예정

#include <bits/stdc++.h>
using namespace std;

typedef long long lld;

int n;
lld t[2048+1];

void update(int p, lld val){
    for(t[p += n] = val; p > 1; p>>=1) t[p>>1] = t[p] + t[p^1];
}

lld query(int l, int r){  // [l, r)
    lld ret = 0;
    for(l += n, r += n; l < r; l >>= 1, r >>= 1){
        if(l&1) ret += t[l++];
        if(r&1) ret += t[--r];
    }
    return ret;
}

int main(){
    int T;
    scanf("%d", &T);
    for(int tc=1; tc<=T; ++tc){
        memset(t, 0, sizeof(t));
        int _n, _m, k, m;
        scanf("%d %d %d", &_n, &_m, &k);
        n = max(_n, _m);
        m = min(_n, _m);
        vector<int> a[m];
        while(k--){
            int s, e;
            scanf("%d %d", &s, &e);
            if(_n <= _m)
                a[s-1].push_back(e-1);
            else
                a[e-1].push_back(s-1);
        }
       
        lld ret = 0;
        for(int i=0; i<m; ++i){
            sort(a[i].begin(), a[i].end());
            for(int j=0; j<a[i].size(); ++j){
                int x = a[i][j];
                ret += query(x+1, n);
                update(x, query(x, x+1)+1);
            }
        }
        printf("Test case %d: %lld\n", tc, ret);
    }
   
    return 0;
}