题目

题意:

有一群牛，每个牛有两个属性值[S,E]，如果牛i和牛j属性值满足Si <= Sj 且 Ej <= Ei 且 Ei - Si > Ej - Sj，牛i比牛j强壮，输出每个牛比自己强壮的牛的数量。

题解：

我们可以把[S,E]看作坐标，条件Si <= Sj 且 Ej <= Ei 且 Ei - Si > Ej - Sj其实就是：求每个点左上角有多少点
我们先将e按照降序，然后s按照升序
这样的话，越往前的牛越弱
我们可以用树状数组来求和计算

代码：

#include <iostream>
using namespace std;
#include <stdio.h>
#include <memory.h>
#include <algorithm>
struct COW{
    int start;
    int end;
    int index;
};
#define maxn 100010
COW cow[maxn];
bool cmp(const struct COW &x, const struct COW &y) {
    if (x.end==y.end)
        return x.start < y.start;
    return x.end > y.end;
}
int n,c[maxn],ans[maxn];
int lowbit(int x) {
    return x&(-x);
}

void add(int i, int val) {
    while (i<=n) {
        c[i]+=val;
        i+=lowbit(i);
    }
} 
//求前i项元素的和
int get_sum(int i) {
    int sum=0;
    while (i>0) {
        sum+=c[i];
        i-=lowbit(i);
    }
    return sum;
}
int main()
{
    int i,j,k;

    scanf("%d",&n);
    while (n!=0) {
        for (i=0;i<n;i++) {
            scanf("%d%d",&cow[i].start,&cow[i].end);
            cow[i].start++;
            cow[i].end++;
            cow[i].index=i;
        }
        memset(c,0,sizeof(c));
        sort(cow,cow+n,cmp);
        for (i=0;i<n;i++) {
            if (i>0&&cow[i].start==cow[i-1].start&&cow[i].end==cow[i-1].end)
                ans[cow[i].index]=ans[cow[i-1].index];
            else 
                ans[cow[i].index]=get_sum(cow[i].start);
            add(cow[i].start,1);
        }
        for (i=0;i<n;i++)
            printf("%d%c",ans[i],i==(n-1)?'\n':' ');
        scanf("%d",&n);
    }
    return 0;
}