题意：有N条牛它们有一个自己的区间[s,e];题目输出的是有多少条牛能胜过自己，胜过的意思是如果牛j的区间能完全覆盖牛i的区间即为胜过。
思路：这个可以转换到数轴上理解了，下图就为cow[j]胜过cow[i]；
所以只需先对左端点从小到大，右端点从大到小排序；再查询从右端点到最大值之间有多少个就是答案了，需要注意的是如果区间重合就不需要重复算。
代码：
#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> using namespace std; #define maxn 200009 #define lson left,mid,rt<<1 #define rson mid+1,right,rt<<1 | 1 int sum[maxn << 2]; int Count[maxn]; struct node { int i, st, et; void input(int s, int e, int ii) { i = ii; st = s; et = e; } bool operator < (const node &b)const { return st < b.st || (st == b.st && et > b.et); } } cow[maxn]; void push_up(int rt) { sum[rt] = sum[rt << 1] + sum[rt << 1 | 1]; } void build(int left, int right, int rt) { sum[rt] = 0; if(left == right) return ; int mid = (left + right) >> 1; build(lson); build(rson); } void updata(int p, int left, int right, int rt) { if(left == right) { sum[rt]++; return ; } int mid = (left + right) >> 1; if(p <= mid) updata(p, lson); else updata(p, rson); push_up(rt); } int query(int L, int R, int left, int right, int rt) { if(L <= left && R >= right) return sum[rt]; int ret = 0; int mid = (left + right) >> 1; if(L <= mid) ret += query(L, R, lson); if(R > mid) ret += query(L, R, rson); return ret; } int main() { int n, i; while(scanf("%d", &n), n) { int s, e; memset(Count, 0, sizeof(Count)); for(i = 0; i < n; i++) { scanf("%d%d", &s, &e); cow[i].input(s, e, i); } build(1, n, 1); sort(cow, cow + n); for(i = 0; i < n; i++) { if(i && cow[i].st == cow[i - 1].st && cow[i].et == cow[i - 1].et) Count[cow[i].i] = Count[cow[i - 1].i]; else Count[cow[i].i] = query(cow[i].et, n, 1, n, 1); updata(cow[i].et, 1, n, 1); } printf("%d", Count[0]); for(i = 1; i < n; i++) printf(" %d", Count[i]); printf(" "); } return 0; }