随笔-68  评论-10  文章-0  trackbacks-0
题目链接:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2176
RMQ问题,《算法竞赛入门经典——训练指南》上的例题。
#include <iostream>
#include 
<cstdio>
#include 
<algorithm>
#include 
<cmath>
using namespace std;
const int maxn = 100005;

int n, q;
int a[maxn];
int len;
int val[maxn], cnt[maxn];
int num[maxn], lef[maxn], rig[maxn];
int d[maxn][20];

void RLE_proc() {
    len 
= 0;
    
for(int i = 0; i < n; ) {
        
int j = i + 1;
        
while(a[j] == a[i] && j < n) j++;
        val[len] 
= a[i];
        cnt[len] 
= j - i;
        
for(int k = i; k < j; k++{
            num[k] 
= len;
            lef[k] 
= i;
            rig[k] 
= j - 1;
        }

        len
++;
        i 
= j;
    }

}


void RMQ_init() {
    
for(int i = 0; i < len; i++) d[i][0= cnt[i];
    
for(int j = 1; (1<<j) <= len; j++)
        
for(int i = 0; i + (1<<j) - 1 < len; i++)
            d[i][j] 
= max(d[i][j-1], d[i + (1<<(j-1))][j-1]);
}


int RMQ_query(int a, int b) {
    
int k = int(log(b-a+1/ log(2.0));
    
return max(d[a][k], d[b- (1<<k) + 1][k]);
}


int main()
{
    
while(scanf("%d"&n) != EOF && n) {
        scanf(
"%d"&q);
        
for(int i = 0; i < n; i++) scanf("%d"&a[i]);
        RLE_proc();
        RMQ_init();
        
int a, b;
        
for(int i = 0; i < q; i++{
            scanf(
"%d%d"&a, &b);
            a
--;
            b
--;
            
if(num[a] == num[b]){
                printf(
"%d\n", b-a+1);
            }
 else {
                
int ans = max(rig[a]-a+1, b-lef[b]+1);
                
if(num[a]+1 <= num[b]-1{
                    ans 
= max(ans, RMQ_query(num[a]+1, num[b]-1));
                }

                printf(
"%d\n", ans);
            }

        }

    }

    
return 0;
}


posted on 2013-06-15 17:34 wuxu 阅读(226) 评论(0)  编辑 收藏 引用 所属分类: 数据结构

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