POJ 3067 Japan 2 Dツリー配列

いいテーマです.
地図の上で、西は上から下まで均等に1列の点を並べて、東もこのようにして、それからいくつかの辺を与えて、すべて西の点から東の点までつながっています.最后にこれらの辺の交点を闻いて、いわゆる交点、2つの辺が交差して得た交点で、もし交点が结点の上でならば、算数しません.
まず基本的な方法を考えてみると、ある辺と交わる辺の数が、東と西の番号に関係していることがわかりやすい.すると、ある辺の西の番号がこの辺より大きく、東の番号がこの辺より小さい場合、交差が発生します.もちろん、ある辺の西の番号がこの辺より小さく、東の番号がこの辺より大きい場合、交差も発生します.しかし、両方とも計算すると、明らかに計算が繰り返されるので、前のものを取って計算します.
では、西の結点から、上から下まで、各辺に対して、条件に合った辺を観察して、それから和を求めますが、テーマが与えた辺数は百万に達する可能性があります.直接列挙すれば明らかに頼りにならない.
このとき、モデルを変換して、西の頂点をx軸、東の頂点をy軸として直角座標系を確立することを想像してみましょう.すると、問題は、各点について、右下の点の個数を見て、和を求めます.
このとき木の配列を使うことは難しくありません.
木の配列は2次元で、各辺に対して、座標で挿入する時、1次元のxは減少するべきで、2次元のyは増加して、この座標を挿入した後で、そのxより小さくて、しかもyが大きいのは統計する時すべてこの座標を統計することができます.そして和を求めるときは逆です.

/*
ID: sdj22251
PROG: subset
LANG: C++
*/
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <map>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define MAXN 100007
#define INF 1000000000
#define eps 1e-7
using namespace std;
int a[1005][1005];
int xx[1000005], yy[1000005];
int n, m;
int lowbit(int x)
{
    return x & -x;
}
void modify(int x, int y)
{
    for(int i = x; i >= 1; i -= lowbit(i))
        for(int j = y; j <= m; j += lowbit(j))
            a[i][j]++;
}
long long get_sum(int x, int y)
{
    long long sum = 0;
    for(int i = x + 1; i <= n; i += lowbit(i))
        for(int j = y - 1; j >= 1; j -= lowbit(j))
            sum += a[i][j];
    return sum;
}
int main()
{
    int T, k, cas = 0;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d%d%d", &n, &m, &k);
        for(int i = 0; i <= n; i++)
            for(int j = 0; j <= m; j++)
                a[i][j] = 0;
        for(int i = 0; i < k; i++)
        {
            scanf("%d%d", &xx[i], &yy[i]);
            modify(xx[i], yy[i]);
        }
        long long ans = 0;
        for(int i = 0; i < k; i++)
            ans += get_sum(xx[i], yy[i]);
        printf("Test case %d: %I64d
", ++cas, ans);
    }
    return 0;
}