gzwzm06
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  1 随笔 :: 52 文章 :: 17 评论 :: 0 Trackbacks
POJ 3368 (RMQ)
  1#include <cstdio>
  2#include <cmath>
  3
  4const int SIZE = 100101;
  5
  6int arr[SIZE], N;
  7int cntFront[SIZE], cntBack[SIZE];
  8int Max[18][SIZE];
  9
 10inline int GetMax(const int& a, const int& b)
 11{
 12    return (a > b ? a : b);
 13}
 14
 15void Init()
 16{
 17    int i, cnt;
 18
 19    cntFront[1] = 1;
 20    cnt = 1;
 21    for ( i = 2; i <= N; ++i )
 22    {
 23        if ( arr[i] != arr[i - 1] )
 24        {
 25            cnt = 1;
 26        }
 27        else {
 28            cnt++;
 29        }
 30        cntFront[i] = cnt;
 31    }
 32
 33    cntBack[N] = 1;
 34    cnt = 1;
 35    for ( i = N - 1; i > 0; --i )
 36    {
 37        if ( arr[i] != arr[i + 1] )
 38        {
 39            cnt = 1;
 40        }
 41        else
 42        {
 43            cnt++;
 44        }
 45        cntBack[i] = cnt;
 46    }
 47}
 48
 49void MakeRMQ()
 50{
 51    int i, j;
 52
 53    for ( i = 1; i <= N; ++i )
 54    {
 55        Max[0][i] = cntFront[i];
 56    }
 57
 58    for ( j = 1; (1 << j) <= N; ++j )
 59        for ( i = 1; i + (1 << j) - 1 <= N; ++i )
 60        {
 61            Max[j][i] = GetMax( Max[j - 1][i], Max[j - 1][i + (1 << (j - 1))] );
 62        }
 63}
 64
 65inline int RMQ(const int& i, const int& j)
 66{
 67    int k = (int)(log((double)(j - i + 1)) / log(2.0));
 68
 69    return GetMax( Max[k][i], Max[k][j - (1 << k) + 1] ) ;
 70}
 71
 72int Query(int s, int e)
 73{
 74    if ( s == e )
 75        return 1;
 76    else 
 77    {
 78        int t, lv, rv;
 79
 80        lv = cntBack[s];
 81        rv = cntFront[e];
 82
 83        if ( s + lv - 1 > e - rv + 1 )
 84        {
 85            return (e - s + 1);
 86        }
 87
 88        t = GetMax( lv, rv );
 89
 90        s = s + lv;
 91        e = e - rv;
 92
 93        if ( s < e )
 94        {
 95            t = GetMax( t, RMQ( s, e ) );
 96        }
 97
 98        return t;
 99
100    }
101}
102
103int main()
104{
105//    freopen("1.txt", "r", stdin);
106
107    int i, s, e, Q;
108
109    while ( scanf("%d", &N) , N != 0 )
110    {
111        scanf("%d", &Q);
112
113        for ( i = 1; i <= N; ++i )
114        {
115            scanf("%d", &arr[i]);
116        }
117        
118        Init();
119        MakeRMQ();
120
121        for ( i = 0; i < Q; ++i )
122        {
123            scanf("%d %d", &s, &e);
124
125            printf("%d\n", Query( s, e ));
126
127        }
128
129    }
130
131    return 0;
132}
posted on 2009-05-08 08:00 巫 阅读(127) 评论(0)  编辑 收藏 引用 所属分类: 数据结构

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