POJ – 2352 Stars 树状数组 略坑

注意建树范围开大一点。

x 先让其 +1 ，树状数组不能维护0 这个点。

int n;
int c[32005];

struct Point {
    int x, y;
    Point(int _x = 0, int _y = 0) {
        x = _x;
        y = _y;
    }
    friend bool operator < (const Point& a, const Point& b) {
        if (a.y == b.y) return a.x < b.x;
        return a.y < b.y;
    }
};

Point p[15005];

int ask(int x) {
    int ans = 0;
    for (; x; x -= x & -x) ans += c[x];
    return ans;
}

void add(int x, int y) {
    for (; x <= 32005; x += x & -x) c[x] += y;
}

int ans[15005];

int main() {
    int x, y;
    n = readint();
    for (int i = 1; i <= n; i++) {
        x = readint(), y = readint();
        p[i] = Point(x + 1, y);
    }
    sort(p + 1, p + n + 1);
    for (int i = 1; i <= n; i++) {
        ans[ask(p[i].x)]++;
        add(p[i].x, 1);
    }
    for (int i = 0; i < n; i++) {
        Put(ans[i]);
        puts("");
    }
}