学步园

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;
}