重工电子论坛

 找回密码
 立即注册

QQ登录

只需一步,快速开始

搜索
热搜: 活动 交友 discuz
查看: 53|回复: 0

[其他] 【RMQ(倍增算法)模版】

[复制链接]

6

主题

6

帖子

26

积分

新手上路

Rank: 1

积分
26
发表于 2018-6-13 23:06:33 | 显示全部楼层 |阅读模式
本帖最后由 love 于 2018-6-14 13:57 编辑

[AppleScript] syntaxhighlighter_viewsource syntaxhighlighter_copycode
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int n,m;
int Min[50001][32],Max[50001][32];
int main(){
	int a,b;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		scanf("%d",&Min[i][0]);
		Max[i][0]=Min[i][0];
	}
	for(int j=1;j<=floor(log2(n));j++){
		for(int i=1;i<=n-(1<<j)+1;i++){
			Max[i][j]=max(Max[i][j-1],Max[i+(1<<(j-1))][j-1]);
			Min[i][j]=min(Min[i][j-1],Min[i+(1<<(j-1))][j-1]);
		}
	}
	for(int i=1;i<=m;i++){
		scanf("%d%d",&a,&b);
		int k=floor(log2(b-a+1));
		printf("%d\n",max(Max[a][k],Max[b-(1<<k)+1][k])-min(Min[a][k],Min[b-(1<<k)+1][k]));
	}
}

注意数组含义:Min[j]表示从第i个点开始,连续的长度为(1<<j)的区间的极值
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

Archiver|手机版|小黑屋|cqutlab ( 渝ICP备15004556号

GMT+8, 2018-8-19 07:30 , Processed in 0.091988 second(s), 26 queries .

Powered by Discuz! X3.1

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表