gzwzm06
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  1 随笔 :: 52 文章 :: 17 评论 :: 0 Trackbacks
POJ 2528(离散化 + 线段树)
  1#include <cstdio>
  2#include <memory.h>
  3#include <algorithm>
  4using namespace std ;
  5
  6const int MAXN = 41001 ;
  7const int SIZE = 10001 ;
  8
  9struct NODE
 10{
 11    int m_flag ;
 12    int m_start, m_end ;
 13    NODE *leftc , *rightc ;
 14    
 15    void BuildTree(const int& s, const int& e) ;
 16    void Insert(const int& s, const int& e, const int& k) ;
 17    void FindInTree() ;
 18} ;
 19
 20struct WALL
 21{
 22    int m_pos ;
 23    int m_value ;
 24
 25    bool const operator < ( WALL& b )const
 26    {
 27        if ( m_value < b.m_value )
 28            return true ;
 29        return false ;
 30    }
 31}wall[SIZE * 2] ;
 32
 33NODE *root ;
 34NODE Stree[MAXN] ;
 35int g_Pos ;
 36int ans , arrSize ;
 37int gFlag[SIZE] ;
 38
 39void NODE::BuildTree(const int& s, const int& e)
 40{
 41    m_flag = 0 ;
 42    m_start = s, m_end = e ;
 43    if ( e == s )
 44    {
 45        leftc = rightc = NULL ;
 46        return ;
 47    }
 48    
 49    int mid = ( s + e ) >> 1 ;
 50    
 51    leftc = &Stree[g_Pos++] ;
 52    rightc = &Stree[g_Pos++] ;
 53    
 54    leftc->BuildTree(s, mid) ;
 55    rightc->BuildTree(mid + 1, e) ;    
 56    
 57}
 58
 59void NODE::Insert(const int& s, const int& e, const int& k)
 60{
 61    if ( m_start == m_end )
 62    {
 63        m_flag = k ;
 64        return ;
 65    }
 66    if ( m_start == s && m_end == e )
 67    {
 68        m_flag = k ;
 69        return ;
 70    }    
 71    if ( m_flag > 0 ){
 72        rightc->m_flag = m_flag ;
 73        leftc->m_flag = m_flag ;
 74        m_flag = -1 ;
 75    }
 76    else if ( m_flag == 0 )
 77        m_flag = k ;
 78    
 79    int mid = ( m_start + m_end ) >> 1 ;
 80    
 81    if ( mid >= e )
 82    {
 83        leftc->Insert( s, e, k ) ;
 84    }
 85    else if ( mid < s ) //就这里，写多了一个等号，导致WA十几次
 86    {
 87        rightc->Insert( s, e, k ) ;
 88    }
 89    else {
 90        leftc->Insert( s, mid, k ) ;
 91        rightc->Insert( mid + 1, e, k ) ;
 92    }
 93}
 94
 95void NODE::FindInTree()
 96{
 97    if ( m_flag >= 0  )
 98    {
 99        if ( gFlag[m_flag] == 0 )
100        {
101            gFlag[m_flag] = 1 ;
102            ans++ ;
103        }
104        return ; //不需要访问到叶节点
105    }
106    
107    if ( m_flag == -1 )
108    {
109        leftc->FindInTree() ;
110        rightc->FindInTree() ;
111    }
112    
113}
114
115void Init()
116{
117    ans = 0 ;
118    g_Pos = 1 ;
119    root = &Stree[0] ;
120    
121    root->leftc = root->rightc = NULL ;
122    memset(gFlag, 0, sizeof(gFlag)) ;
123}
124int main()
125{
126//     freopen("in.txt", "r", stdin) ;
127    
128    int T , n , i , size , x , y ;
129    int pos[SIZE][2] ;
130    scanf("%d", &T) ;
131    
132    while ( T-- )
133    {
134        Init() ;
135        size = 0 ;
136        
137        scanf("%d", &n) ;
138        
139        for ( i = 1 ; i <= n ; ++i )
140        {
141            scanf("%d %d", &pos[i][0], &pos[i][1]) ;
142            wall[size].m_pos = i ;
143            wall[size++].m_value = pos[i][0] ;
144            wall[size].m_pos = -i ;
145            wall[size++].m_value = pos[i][1] ;
146        }
147        //离散化
148        sort(wall, wall + size) ;
149        
150        x = 1 ;
151        if ( wall[0].m_pos < 0 )
152            pos[-wall[0].m_pos][1] = 1 ;
153        else
154            pos[wall[0].m_pos][0] = 1 ;
155        
156        for ( i = 1 ; i < size ; ++i )
157        {
158            if ( wall[i].m_value != wall[i - 1].m_value )
159            {
160                x++ ;
161            }
162            if ( wall[i].m_pos > 0 )
163                pos[wall[i].m_pos][0] = x ;
164            else 
165                pos[-wall[i].m_pos][1] = x ;
166            
167        }
168        
169        arrSize = x ;
170        //线段树
171        root->BuildTree( 1, arrSize ) ;
172        
173        for ( i = 1 ; i <= n ; ++i )
174        {
175            x = pos[i][0] ;
176            y = pos[i][1] ;
177            root->Insert( x, y, i ) ;
178        }
179        
180        root->FindInTree() ;
181 
182        printf("%d\n", ans) ;
183    }
184    return 0 ;
185}
186
187
188
189
posted on 2008-11-16 20:58 巫 阅读(425) 评论(0)  编辑 收藏 引用 所属分类: 数据结构

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