gzwzm06
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  1 随笔 :: 52 文章 :: 17 评论 :: 0 Trackbacks
Pku 2777(线段树)
  1#include <stdio.h>
  2#include <memory.h>
  3
  4const long max = 200001 ;
  5
  6struct NODE
  7{
  8    int color ;
  9    int start ;
 10    int end ;
 11    struct NODE *leftc ;
 12    struct NODE *rightc ;
 13    
 14    void BuildSTree( int s, int e ) ;
 15    void Insert( int s, int e, int col ) ;
 16    void CountColor( int s, int e ) ;
 17};
 18
 19NODE STree[max] ;
 20NODE *root ;
 21
 22long num = 0 ;
 23bool Color[31] ;
 24
 25void NODE::BuildSTree( int s , int e )
 26{
 27    start = s ;
 28    end = e ;
 29    color = 1 ;
 30
 31    if ( s == e )
 32    {
 33        leftc = NULL ;
 34        rightc = NULL ;
 35        return ;
 36    }
 37
 38    int mid = ( s + e ) >> 1 ;
 39
 40    leftc = &STree[num++] ;
 41    rightc = &STree[num++] ;
 42
 43    leftc->BuildSTree( s , mid ) ;
 44    rightc->BuildSTree( mid + 1 , e ) ;
 45}
 46
 47void NODE::Insert( int s , int e , int col )
 48{
 49    if ( col == color )
 50    {
 51        return ;
 52    }
 53    if ( s == start && e == end )
 54    {
 55        color = col ;
 56        return ;
 57    }
 58    if ( color > 0 )
 59    {
 60        leftc->color = color ;
 61        rightc->color = color ;
 62    }
 63    int mid = ( start + end ) >> 1 ;
 64
 65    color = -1 ;
 66
 67    if ( mid >= e )
 68    {
 69        leftc->Insert( s, e, col ) ;
 70    }
 71    else if ( mid < s ) {
 72        rightc->Insert(  s, e, col ) ;
 73    }
 74    else {
 75        leftc->Insert( s, mid, col ) ;
 76        rightc->Insert( mid + 1, e, col ) ;
 77    }
 78}
 79
 80void Paint( int s , int e , int col )
 81{
 82    root->Insert( s, e, col ) ;
 83}
 84
 85void NODE::CountColor( int s, int e )
 86{
 87    if ( color > 0 )
 88    {
 89        Color[color] = true ;
 90        return ;
 91    }
 92
 93    int mid = ( start + end ) >> 1 ;
 94
 95    if ( mid >= e )
 96    {
 97        leftc->CountColor( s, e ) ;
 98    }
 99    else if ( mid < s ) {
100        rightc->CountColor( s, e ) ;
101    }
102    else {
103        leftc->CountColor( s, mid ) ;
104        rightc->CountColor( mid + 1, e ) ;
105    }  
106}
107
108int main()
109{
110    long L , T , O , s , e ;
111    char cmd ;
112    int col ;
113
114    scanf("%ld %ld %ld\n", &L, &T, &O) ;
115
116    root = &STree[num++] ;
117    root->BuildSTree( 1 , 100000 ) ;
118
119    for ( int i = 0 ; i < O ; i++ )
120    {
121        scanf("%c", &cmd) ;
122
123        while ( cmd != 'C' && cmd != 'P' )
124        {
125            scanf("%c", &cmd) ;
126        }
127
128        if ( cmd == 'C' )
129        {
130            scanf("%ld %ld %d", &s, &e, &col) ;
131            
132            if ( s > e )
133            {
134                long t = s ; s = e ; e = t ;
135            }
136
137            Paint( s, e, col ) ;
138        }
139        else if ( cmd == 'P' )
140        {
141            scanf("%ld %ld", &s, &e) ;
142            
143            if ( s > e )
144            {
145                long t = s ; s = e ; e = t ;
146            }
147
148            root->CountColor( s, e ) ;
149
150            int ans = 0 ;
151            
152            for ( int j = 1 ; j < 31 ; j++ )
153            {
154                if ( Color[j] )
155                {
156                    ans++ ;
157                }
158            }
159
160            memset(Color, 0, sizeof(Color)) ;
161
162            printf("%d\n", ans) ;
163        }
164    }
165
166    return 0 ;
167}
168
posted on 2008-11-17 22:55 巫 阅读(235) 评论(0)  编辑 收藏 引用 所属分类: 数据结构

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