學步園

e 降序   e 相等的時候s升序

排序後可以保證 Ei >= Ei+1

這時候只要找到 在 Si  左邊有多少數就可以找到 有多少種滿足  Ei >= Ej  &&  Si <= Sj  &&  Ei  - Si >= Ej - Sj 可以出來看看

Si 左邊有多少個數就是找早0- Si 區間內有多少個數 用樹狀數組解決

注意輸出的順序 是 原來輸入時候的順序。  排序後順序亂了 所以要保存 輸入時候的順序

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int const MAXN = 100010;
int c[MAXN * 2];
int n;
struct Point{
    int s,e;
    int sum,pos;
}p[MAXN];
bool cmp1(Point x,Point y){
    if(x.e == y.e) return x.s < y.s;
    return x.e > y.e;
}
bool cmp2(Point x,Point y){
    return x.pos < y.pos;
}
int LowBit(int x){
    return x & (-x);
}
void Add(int x,int d){
    while(x <= MAXN){
        c[x] += d;
        x += LowBit(x);
    }
}
int Sum(int x){
    int ret = 0;
    while(x > 0){
        ret += c[x];
        x -= LowBit(x);
    }
    return ret;
}
int main(){
    while(~scanf("%d",&n),n){
        memset(c,0,sizeof(c));
        for(int i = 1;i <= n;i++){
            scanf("%d%d",&p[i].s,&p[i].e);
            p[i].s++;
            p[i].e++;
            p[i].pos = i;
        }
        sort(p+1,p+n+1,cmp1);
        p[1].sum = 0;
        Add(p[1].s,1);
        for(int i = 2;i <= n;i++){
            if(p[i].e == p[i - 1].e && p[i].s == p[i -1 ].s){
                p[i].sum = p[i - 1].sum;
            }
            else p[i].sum = Sum(p[i].s);
            Add(p[i].s,1);
        }
        sort(p+1,p+n+1,cmp2);
        for(int i = 1; i < n;i++){
            printf("%d ",p[i].sum);
        }
        printf("%d\n",p[n].sum);
    }
    return 0;
}