poj2481 树状数组

排序后类似stars， 用树状数组。

注意两个数组都要memset和去重

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
struct data{
    int s, e, i;
    friend bool operator <(data a, data b){
        if (a.e != b.e) return a.e > b.e;
        else return a.s<b.s;
    }
} a[100010];
int t[100010];
int lowbit(int x){
    return x & -x;
}
void build(int x){
    while (x <= 100001){
        t[x] ++;
        x += lowbit(x);
    }
}
int sum(int x){
    int res = 0;
    while (x){
        res += t[x];
        x -= lowbit(x);
    }
    return res;
}
int ans[100010];
int main(){
    int n;
    while (scanf("%d", &n) && n){
        memset(ans, 0, sizeof(ans));
        memset(t, 0, sizeof(t));
        for (int i = 0; i < n; i++) {scanf("%d%d", &a[i].s, &a[i].e);
        a[i].s++; a[i].e++; a[i].i = i;}
        sort(a, a + n);
        build(a[0].s);
        for (int i = 1; i < n; i++){
            if (a[i].s == a[i-1].s && a[i].e == a[i-1].e) {
                ans[a[i].i] = ans[a[i-1].i];
                build(a[i].s);
                continue;
            }
            ans[a[i].i] = sum(a[i].s);
            //cout<<a[i].i<<"    "<<a[i].s<<' '<<a[i].e<<' '<<ans[a[i].i]<<endl;
            build (a[i].s);
        }
        for (int i = 0; i < n-1; i++) printf("%d ", ans[i]); printf("%d", ans[n-1]);
        printf("\n");
    }
    return 0;
}