题意：给出n头牛的s,e 如果有两头牛，现在si <= sj && ei >= ej
那么称牛i比牛j强壮 然后问每头牛都有几头牛比它强壮
先按照s从小到大排序，然后用e来当做树状数组里面那个a数组，对于每头牛求出前面比他大的e有多少个
还有就是注意有两头牛的s和e相等的情况，就只需要更新值，
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include <cmath> 5 #include<stack> 6 #include<vector> 7 #include<map> 8 #include<set> 9 #include<queue> 10 #include<algorithm> 11 using namespace std; 12 13 typedef long long LL; 14 const int INF = (1<<30)-1; 15 const int mod=1000000007; 16 const int maxn=100005; 17 18 int a[maxn]; 19 int c[maxn];//树状数组 20 int ans[maxn];// 21 22 struct node{ 23 int s,e; 24 int id; 25 } p[maxn]; 26 27 int cmp(node n1,node n2){ 28 if(n1.s != n2.s) return n1.s < n2.s; 29 return n1.e > n2.e; 30 } 31 32 int n; 33 34 int lowbit(int x){ return x & (-x);} 35 36 int sum(int x){ 37 int ret=0; 38 while( x>0){ 39 ret+=c[x];x-=lowbit(x); 40 } 41 return ret; 42 } 43 44 void add(int x,int d){ 45 while(x < maxn){ 46 c[x]+=d; x+=lowbit(x); 47 } 48 } 49 50 int main(){ 51 while(scanf("%d",&n)!=EOF){ 52 if(n == 0) break; 53 for(int i=1;i<=n;i++) scanf("%d %d",&p[i].s,&p[i].e),p[i].id=i; 54 sort(p+1,p+n+1,cmp); 55 56 memset(c,0,sizeof(c)); 57 memset(ans,0,sizeof(ans)); 58 59 for(int i=1;i<=n;i++){ 60 61 if(i!=1 && p[i].s == p[i-1].s && p[i].e == p[i-1].e) ans[p[i].id] = ans[p[i-1].id]; 62 else { 63 ans[p[i].id] = (i-1 ) - sum(p[i].e-1); 64 } 65 add(p[i].e,1); 66 } 67 68 printf("%d",ans[1]); 69 for(int i=2;i<=n;i++) printf(" %d",ans[i]); 70 printf(" "); 71 } 72 return 0; 73 }