POJ 2181 Cows 树状数组

题意：有一些牛，这些牛有一个属性值，这个属性值的范围给出，为si,ei,若si <= sj && ei >= ej && ei - si > ej - sj，则称牛i是比牛j强壮的。问对于每只牛，有多少只牛比其强壮。
思路：树状数组，可以对e按升序排序，这样在j前面的e值一定比j的e值大，因此只需要考虑s值即可，就可以用树状数组了。这道题也从根本上改变了我对树状数组的认识。树状数组不仅可以在一维上使用，而且可以在二维上使用，甚至在关系上使用。这时，我们可以先固定一维，然后对另一维使用树状数组。这道题受益很多。
代码：
[cpp]
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string.h>
using namespace std;

const int N = 100010;
struct interval{
    int lp,rp,id,cnt;
}rr[N];
int num[N];
bool cmp1(interval a,interval b){
    if(a.rp == b.rp)
        return a.lp < b.lp;
    return a.rp > b.rp;
}
bool cmp2(interval a,interval b){
    return a.id < b.id;
}
int lowbit(int x){
    return x & (-x);
}
int sum(int x){
    int s = 0;
    while(x > 0){
      s += num[x];
      x -= lowbit(x);
    }
    return s;
}
void update(int pos,int add){
    while(pos < N){
       num[pos] += add;
       pos += lowbit(pos);
    }
}
int main(){
    //freopen("1.txt","r",stdin);
    int n;
    while(scanf("%d",&n) && n){
       int x,y;
       memset(num,0,sizeof(num));
       for(int i = 0; i < n; ++i){
          scanf("%d%d",&x,&y);
          rr[i].lp = x + 1;
          rr[i].rp = y + 1;
          rr[i].id = i; rr[i].cnt = 0;
       }
       sort(rr,rr+n,cmp1);
       for(int i = 0; i < n; ++i){
          int xx = rr[i].lp;
          int yy = rr[i].rp;
          rr[i].cnt = sum(rr[i].lp);
          int s = 0;
          for(int j = i - 1; j >= 0; --j){
             if((rr[j].lp != rr[i].lp) || (rr[j].rp != rr[i].rp))
                  break;
             s++;
          }
          rr[i].cnt -= s;
          update(xx,1);
          update(yy+1,-1);
       }
       sort(rr,rr+n,cmp2);
       for(int i = 0; i < n; ++i){
          if(i != n-1)
              printf("%d ",rr[i].cnt);
          else
              printf("%d\n",rr[i].cnt);
       }
    }
    return 0;
}

补充：软件开发 , C++ ,