poj 2481 Cows(樹狀數組)

poj 2481 Cows(樹狀數組)

題目鏈接：poj 2481 Cows

題目大意：給定若干的區間，問說每個區間被多少個區間完全包含。

解題思路：將區間按照區間左端點小的，右端點大的排序，然後掃描一遍，每次查詢[r，maxn]，然後在r處添加1。注意

區間相同的情況，需要添加，但是不需要查詢，直接和前一個的是相同的。

#include 
#include 
#include 

using namespace std;
const int maxn = 1e5 + 1;
#define lowbit(x) ((x)&(-x))

int N, fenw[maxn + 5], ans[maxn + 5];
struct Seg {
    int l, r, id;
    friend bool operator < (const Seg& a, const Seg& b) {
        if (a.l != b.l)
            return a.l < b.l;
        return a.r > b.r;
    }
}s[maxn + 5];

void add (int x, int w) {
    while (x <= maxn) {
        fenw[x] += w;
        x += lowbit(x);
    }
}

int sum (int x) {
    int ret = 0;
    while (x) {
        ret += fenw[x];
        x -= lowbit(x);
    }
    return ret;
}

int main () {
    while (scanf("%d", &N) == 1 && N) {
        memset(fenw, 0, sizeof(fenw));
        for (int i = 1; i <= N; i++) {
            scanf("%d%d", &s[i].l, &s[i].r);
            s[i].l++, s[i].r++, s[i].id = i;
        }

        sort(s + 1, s + N + 1);

        for (int i = 1; i <= N; i++) {
            if (i != 1 && s[i].l == s[i-1].l && s[i].r == s[i-1].r)
                ans[s[i].id] = ans[s[i-1].id];
            else 
                ans[s[i].id] = sum(maxn) - sum(s[i].r - 1);
            add(s[i].r, 1);
        }

        for (int i = 1; i <= N; i++)
            printf("%d%c", ans[i], i == N ? '\n' : ' ');
    }
    return 0;
}