gzwzm06
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  1 随笔 :: 52 文章 :: 17 评论 :: 0 Trackbacks
POJ 3368 Frequent values (线段树)
  1#include <cstdio>
  2
  3const int SIZE = 100101;
  4
  5struct STREE
  6{
  7    int m_start;
  8    int m_end;
  9    int m_left;
 10    int m_right;
 11    int m_num;
 12    int m_srcS;
 13    int m_srcE;
 14    int m_equal;
 15}stree[SIZE * 2];
 16int gIndex = 1;
 17
 18int rs_n;
 19int srcS, srcE;
 20
 21void BuildSTree(const int& id, const int& s, const int& e)
 22{
 23    stree[id].m_start = s;
 24    stree[id].m_end = e;
 25    stree[id].m_srcS = 100000;
 26    stree[id].m_srcE = 0;
 27    stree[id].m_num = 0;
 28    stree[id].m_equal = false;
 29
 30    if ( s == e )
 31    {
 32        stree[id].m_equal = true;
 33        return ;
 34    }
 35
 36    int mid = (s + e) >> 1;
 37
 38    stree[id].m_left = gIndex++;
 39    BuildSTree( stree[id].m_left, s, mid );
 40
 41    stree[id].m_right = gIndex++;
 42    BuildSTree( stree[id].m_right, mid + 1, e );
 43}
 44
 45void Insert(const int& id, const int&p, const int& num)
 46{
 47    if ( stree[id].m_num < num )
 48        stree[id].m_num = num;
 49
 50    if ( stree[id].m_srcS > srcS )
 51        stree[id].m_srcS = srcS;
 52    if ( stree[id].m_srcE < srcE )
 53        stree[id].m_srcE = srcE;
 54
 55    if ( stree[id].m_start == p && stree[id].m_end == p )
 56    {
 57        stree[id].m_srcS = srcS;
 58        stree[id].m_srcE = srcE;
 59        return;
 60    }
 61
 62    int mid = (stree[id].m_start + stree[id].m_end) >> 1;
 63
 64    if ( mid >= p )
 65    {
 66        Insert( stree[id].m_left, p, num );
 67    }
 68    else
 69    {
 70        Insert( stree[id].m_right, p, num );
 71    }
 72}
 73
 74void Query(const int& id, const int& s, const int& e)
 75{
 76    if ( stree[id].m_srcS == s && stree[id].m_srcE == e )
 77    {
 78        if ( rs_n < stree[id].m_num )
 79            rs_n = stree[id].m_num;
 80        return;
 81    }
 82    if ( stree[id].m_equal && stree[id].m_srcS <= s && stree[id].m_srcE >= e )
 83    {
 84        if ( rs_n < e - s + 1 )
 85            rs_n = e - s + 1;
 86
 87        return;
 88    }
 89    int l = stree[id].m_left, r = stree[id].m_right;
 90
 91    if ( stree[l].m_srcE >= e )
 92    {
 93        Query( l, s, e );
 94    }
 95    else if ( s > stree[r].m_srcS )
 96    {
 97        Query( r, s, e );
 98    }
 99    else {
100        Query( l, s, stree[l].m_srcE  );
101        Query( r, stree[r].m_srcS, e );
102    }
103}
104
105int arr[SIZE], N, Q;
106int rs[SIZE][2];
107
108int main()
109{
110    int i, p;
111
112    while ( scanf("%d", &N) && N != 0 )
113    {
114        scanf("%d", &Q);
115        
116        gIndex = 1;
117
118        for ( i = 1; i <= N; ++i )
119        {
120            scanf("%d", &arr[i]);
121        }
122
123        srcS = 1;
124        p = 1;
125        for ( i = 2; i <= N; ++i )
126        {
127            if ( arr[i] != arr[i - 1] )
128            {
129                srcE = i - 1;
130                rs[p][0] = srcS;
131                rs[p][1] = srcE;
132                srcS = i;
133                p++;
134            }
135        }
136        rs[p][0] = srcS;
137        rs[p][1] = N;
138        
139        BuildSTree( 0, 1, p );
140
141        for ( i = 1; i <= p; ++i )
142        {
143            srcS = rs[i][0];
144            srcE = rs[i][1];
145            Insert( 0, i, srcE - srcS + 1 );
146        }
147
148        for ( i = 0; i < Q; ++i )
149        {
150    
151            scanf("%d %d", &srcS, &srcE);
152            rs_n = 0;
153
154            if ( srcS == srcE )
155            {
156                printf("1\n");
157            }
158            else if ( srcS == srcE - 1 )
159            {
160                if ( arr[srcS] == arr[srcE] )
161                    printf("2\n");
162                else
163                    printf("1\n");
164            }
165            else {
166                Query( 0, srcS, srcE );
167                printf("%d\n", rs_n);
168            }
169        }
170
171        
172    }
173
174    return 0;
175}
http://acm.pku.edu.cn/JudgeOnline/problem?id=3368
代码恶心了。。。
posted on 2009-05-08 07:59 巫 阅读(136) 评论(0)  编辑 收藏 引用 所属分类: 数据结构

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