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; 
}