POJ 2352 - Stars

問題

http://poj.org/problem?id=2352

解法

点の座標が(y座標, x座標)の辞書順で昇順になるよう与えられます. ですので各クエリについて, 今までに与えられた頂点の中から, x座標が以下である頂点の個数がその星のレベルとなります. そのような頂点の個数はFenwick treeを使えば時間内に求めることができます.

ソースコード

#include <cstdio>
#include <vector>
using namespace std;

const int MAX_X = 32000;

// 0-indexedのFenwick tree.
// [0, n)を管理する.
// 実装は蟻本と同じだが, 添字を++して0-indexedに見せかけてる.
template <class T>
struct FenwickTree {
    int n;
    vector<int> elt;

    FenwickTree(int size) {
        n = size;
        elt.resize(size + 1, 0);
    }

    void add(int i, T x) {
        i++;
        while (i <= n) {
            elt[i] += x;
            i += i & -i;
        }
    }

    T sum(int i) {
        i++;

        T res = 0;
        while (i > 0) {
            res += elt[i];
            i -= i & -i;
        }
        return res;
    }
};

int main() {
    int n;
    scanf("%d", &n);

    vector<int> counter(n);

    FenwickTree<int> ft(MAX_X + 1);
    for (int i = 0; i < n; i++) {
        int x, y;
        scanf("%d%d", &x, &y);

        counter[ft.sum(x)]++;
        ft.add(x, 1);
    }

    for (int i = 0; i < n; i++) {
        printf("%d\n", counter[i]);
    }

    return 0;
}

感想

セグツリー問題集の2問目(1問目はなんかやったことあった)です. これはやるだけ.