gzwzm06
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  1 随笔 :: 52 文章 :: 17 评论 :: 0 Trackbacks
POJ 2481 Cows(线段树)
  1#include <cstdio>
  2#include <algorithm>
  3using namespace std;
  4
  5const int SIZE = 100001;
  6
  7struct RANGE
  8{
  9    int m_S, m_E;
 10    int m_p;
 11
 12    //按区间右端从大到小排序，再按左端从小到大排
 13    //将左端依序插入线段树，即将区间将大先放入，就能得出包含关系
 14    bool operator < (const RANGE& other)
 15    {
 16        if ( m_E != other.m_E )
 17            return (m_E > other.m_E);
 18        
 19        return (m_S < other.m_S);
 20    }
 21}cow[SIZE];
 22
 23//线段树
 24struct STREE
 25{
 26    int m_leftPos, m_rightPos;
 27    int m_left, m_right;
 28    int m_ItNum;                //记录区间的左端个数
 29}tree[SIZE * 2];
 30
 31int N, result[SIZE];
 32
 33void BuildSTree(int& index, const int& l, const int& r)
 34{
 35    int id = index;
 36    tree[id].m_left = l, tree[id].m_right = r;
 37    tree[id].m_ItNum = 0;
 38    if ( l == r )
 39    {
 40        tree[id].m_leftPos = tree[id].m_rightPos = -1;
 41        return ;
 42    }
 43
 44    int mid = (l + r) >> 1;
 45
 46    tree[id].m_leftPos = ++index;
 47    BuildSTree( index, l, mid );
 48    tree[id].m_rightPos = ++index;
 49    BuildSTree( index, mid + 1, r );
 50}
 51
 52int Insert(const int& id, const int& s)
 53{
 54    int num = 0;
 55    if ( tree[id].m_left == s && tree[id].m_right == s )
 56    {
 57        tree[id].m_ItNum++;
 58        return (tree[id].m_ItNum - 1);
 59    }
 60
 61    int mid = (tree[id].m_left + tree[id].m_right) >> 1;
 62
 63    if ( s <= mid ) {
 64        tree[id].m_ItNum++;
 65        num += Insert(tree[id].m_leftPos, s);
 66    }
 67    else {
 68        num = tree[id].m_ItNum;
 69        num += Insert(tree[id].m_rightPos, s);
 70    }
 71
 72    return num;
 73}
 74
 75int main()
 76{
 77    freopen("1.txt", "r", stdin);
 78    int i, t, maxN;
 79
 80    while ( true )
 81    {
 82        scanf("%d", &N);
 83        if ( N == 0 )
 84            break;
 85        
 86        maxN = 0;
 87        for ( i = 0; i < N; ++i )
 88        {
 89            scanf("%d %d", &cow[i].m_S, &cow[i].m_E);
 90            cow[i].m_p = i;
 91            if ( cow[i].m_E > maxN )
 92                maxN = cow[i].m_E;
 93        }
 94        t = 0;
 95        BuildSTree(t, 0, maxN);
 96        sort(cow, cow + N);
 97
 98        result[cow[0].m_p] = Insert(0, cow[0].m_S);
 99        for ( i = 1; i < N; ++i )
100        {
101            result[cow[i].m_p] = Insert(0, cow[i].m_S);
102            //处理区间相等的情况，插入操作还是照做，结果就为等价
103            if ( cow[i].m_E == cow[i - 1].m_E && cow[i].m_S == cow[i - 1].m_S )
104                result[cow[i].m_p] = result[cow[i - 1].m_p];
105        }
106
107        for ( i = 0; i < N - 1; ++i )
108        {
109            printf("%d ", result[i]);
110        }
111        printf("%d\n", result[i]);
112    }
113    return 0;
114}
posted on 2009-04-11 16:15 巫 阅读(224) 评论(0)  编辑 收藏 引用 所属分类: 数据结构

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理