POJ 3067 Japan

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;

const int maxn = 1e6 + 10;
int T, N, M, K;
int c[maxn];

struct Node{
    int x;
    int y;
}node[maxn];

bool cmp(const Node &a, const Node &b) {
    if(a.x != b.x)
        return a.x < b.x;
    return a.y < b.y;
}

int lowbit(int x) {
    return x & (-x);
}

void add(int i, int val) {
    while(i <= M) {
        c[i] += val;
        i += lowbit(i);
    }
}

int getsum(int x) {
    int ans = 0;
    while(x > 0) {
        ans += c[x];
        x -= lowbit(x);
    }
    return ans;
}

int main() {
    scanf("%d", &T);
    for(int t = 1; t <= T; t ++) {
        memset(c, 0, sizeof(c));
        scanf("%d%d%d", &N, &M, &K);

        for(int i = 1; i <= K; i ++)
            scanf("%d%d", &node[i].x, &node[i].y);

        sort(node + 1, node + 1 + K, cmp);

        long long ans = 0;
        for(int i = 1; i <= K; i ++) {
            printf("!!!%d\n", getsum(M));
            ans += getsum(M) - getsum(node[i].y);
            add(node[i].y, 1);
        }


        printf("Test case %d: %lld\n", t, ans);
    }
    return 0;
}