poj 2481 Cows

点击打开链接poj2481

思路：线段树+单点更新
分析：
1 题目给定n头牛所在的区间，然后问每头牛都有几头牛比它强壮
2 根据题目如果牛i的区间是[Si , Ei]，牛j的区间是[Sj , Ej]那么牛i要比牛j强壮的话那么就有Si <= Sj && Ei >= Ej && Si-Ei != Sj-Ej;
3 那么根据上面的条件，我们应该要先对n头牛的区间排序”按照S从小到大，相同S按照E从大到小排序“，然后就可以利用线段树求了。
4 有一个地方需要注意的是当排完序后相邻的两个相等，那么只须更新不用求和。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

#define MAXN 100010

struct Segment{
   int x;
   int y;
   int number;
   bool operator==(const Segment &a)const{
      if(a.x == x && a.y == y)
        return true;
      return false;
   }
};
Segment s[MAXN];
struct Node{
   int left;
   int right;
   int sum;
};
Node node[4*MAXN];
int n;
int vis[MAXN];

bool cmp(Segment s1 , Segment s2){
   if(s1.x < s2.x)
     return true;
   else if(s1.x == s2.x && s1.y > s2.y)
     return true;
   return false;
}

void buildTree(int left , int right , int pos){
   node[pos].left = left;
   node[pos].right = right; 
   node[pos].sum = 0;
   if(left == right)
     return;
   int mid = (left+right)>>1;
   buildTree(left , mid , pos<<1);
   buildTree(mid+1 , right , (pos<<1)+1);
}

int query(int left , int right , int pos){
   if(node[pos].left == left && node[pos].right == right)
     return node[pos].sum;
   int mid = (node[pos].left+node[pos].right)>>1; 
   if(right <= mid)
     return query(left , right , pos<<1);
   else if(left > mid)
     return query(left , right , (pos<<1)+1);
   else
     return query(left , mid , pos<<1)+query(mid+1 , right , (pos<<1)+1);
}

void update(int index , int pos){
   if(node[pos].left == node[pos].right){
     node[pos].sum++;
     return;
   }
   int mid = (node[pos].left+node[pos].right)>>1;
   if(index <= mid)
     update(index , pos<<1);
   else
     update(index , (pos<<1)+1);
   node[pos].sum = node[pos<<1].sum+node[(pos<<1)+1].sum;
}

int main(){
  while(scanf("%d" , &n) && n){
      memset(vis , 0 , sizeof(vis));
      for(int i = 0 ; i < n ; i++){
         scanf("%d%d" , &s[i].x , &s[i].y);
         s[i].number = i;
      }
      sort(s , s+n , cmp);
      buildTree(1 , MAXN , 1);
      for(int i = 0 ; i < n ; i++){
         if(i && s[i] == s[i-1])
           vis[s[i].number] = vis[s[i-1].number];
         else
           vis[s[i].number] += query(s[i].y , MAXN , 1);
         update(s[i].y , 1);
      }
      printf("%d" , vis[0]);
      for(int i = 1 ; i < n ; i++)
         printf(" %d" , vis[i]);
      printf("\n");
  }
  return 0;
}

思路：树状数组
分析：
1 题目给定n头牛所在的区间，然后问每头牛都有几头牛比它强壮
2 根据题目如果牛i的区间是[Si , Ei]，牛j的区间是[Sj , Ej]那么牛i要比牛j强壮的话，那么就有Si <= Sj && Ei >= Ej && Si-Ei > Sj-Ej;
3 那么根据上面的条件，我们应该要先对n头牛的区间排序”按照S从小到大，相同S按照E从大到小排序“
4 显然排完序之后我们能够满足Si <= Sj && Ei >= Ej，但是我们应该要注意到Si-Ei > Sj-Ej，说明了排完序之后不能够相等
5 我们利用E做树状数组，如果前后两个相当那么直接更新即可

代码:

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int MAXN = 100010;

struct Node{
    int S;
    int E;
    int number;
    bool operator<(const Node& tmp)const{
        if(S < tmp.S) 
            return true;
        else if(S == tmp.S && E > tmp.E) 
            return true;
        return false;
    }
    bool operator==(const Node& tmp)const{
        return S == tmp.S && E == tmp.E; 
    }
};
Node node[MAXN];
int n;
int ans[MAXN];
int treeNum[MAXN];

int lowbit(int x){
    return x&(-x);
}

int getSum(int x){
    int sum = 0;
    while(x){
        sum += treeNum[x];
        x -= lowbit(x);
    }
    return sum;
}

void add(int x , int val){
    while(x < MAXN){
         treeNum[x] += val;
         x += lowbit(x);
    }
}

void solve(){
    memset(ans , 0 , sizeof(ans));
    memset(treeNum , 0 , sizeof(treeNum));
    sort(node , node+n);
    for(int i = 0 ; i < n ; i++){
        int id = node[i].E;
        if(i && node[i] == node[i-1])
           ans[node[i].number] = ans[node[i-1].number];
        else
           ans[node[i].number] += i-getSum(id-1);
        add(id , 1);
    }
    printf("%d" , ans[0]);
    for(int i = 1 ; i < n ; i++)
       printf(" %d" , ans[i]);
    puts("");
}

int main(){
    while(scanf("%d" , &n) && n){
        for(int i = 0 ; i < n ; i++){
            scanf("%d%d" , &node[i].S , &node[i].E);    
            node[i].number = i;
        }
        solve();
    }
    return 0;
}