本文共 1367 字，大约阅读时间需要 4 分钟。

      题目大意：FJ有n头牛(编号为1~n)，每一头牛都有一个测验值（S，E），对于牛i和牛j来说，如果它们的测验值满足下面的条件则表示牛i比牛j强壮：Si <= Sj and Ej <= Ei and Ei - Si > Ej - Sj。现在已知每一头牛的测验值，要求输出每头牛有几头牛比其强壮。

题解：和POJ2352 stars比较像，但是stars给出的数据是排好序了的，本题没有

      首先，我们将一个线段的左右端点(l,r)  l看做是x坐标，r看做是y坐标，那么当一个线段seg2包含另一个线段seg1的时候，即是

       seg2.l<seg1.l && seg2.r>seg1.r ,它们的位置关系则是这样

        那么我们先对线段按照y从大到小排序，然后对于每一个点，x坐标比它小的就是可以包含的线段。

 

       有一个坑点，就是给的线段有可能是一样的，就是可能会有两条线段的左右端点完全相等，这个时候要特殊处理

       还有记得ans数组要清0.........

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include "algorithm"using namespace std;struct node{ int l,r,id;}a[100010];int ans[100010];int c[100010];int n;int lowbit(int x){ return x & -x;}void add(int i,int val)// Add操作，将第i个元素增加val，那么他的父节点也要增加+{ while(i<=n)//注意判断这里不一定是n，这里应该是数值a[i]能达到的最大的值 { c[i]+=val; i+=lowbit(i);//i的父节点 }}bool cmp(node a,node b){ if(a.r==b.r)return a.l
           
            b.r;}int sum(int i){ int s=0; while(i>0) { s+=c[i]; i-=lowbit(i);//I的前驱 } return s;}int main(){ //freopen("input.txt","r",stdin); while(~scanf("%d",&n) && n) { for(int i=1;i<=n;++i) { scanf("%d%d",&a[i].l,&a[i].r); a[i].l++;a[i].r++; a[i].id=i; } sort(a+1,a+1+n,cmp); memset(c,0,sizeof(c)); memset(ans,0,sizeof(ans)); for(int i=1;i<=n;++i) { if(i!=1 && a[i].l==a[i-1].l && a[i].r==a[i-1].r) ans[a[i].id]=ans[a[i-1].id]; else ans[a[i].id]=sum(a[i].l); add(a[i].l,1); } for(int i=1;i