P1816 忠诚

题目描述

老管家是一个聪明能干的人。他为财主工作了整整 年。财主为了让自已账目更加清楚，要求管家每天记 次账。由于管家聪明能干，因而管家总是让财主十分满意。

但是由于一些人的挑拨，财主还是对管家产生了怀疑。于是他决定用一种特别的方法来判断管家的忠诚。他把每次的账目按 编号，然后不定时地问管家这样的问题：在 到 号账中最少的一笔是多少？

为了让管家没时间作假，他总是一次问多个问题。

输入格式

第一行输入两个数 ，表示有 笔账和 个问题。
第二行输入 个数，分别表示账目的钱数。
接下来 行分别输入 个问题，每行 个数字，分别表示开始的账目编号 和结束的账目编号 。

输出格式

第一行输出每个问题的答案，每个答案中间以一个空格分隔。

输入输出样例 #1

输入 #1

10 3
1 2 3 4 5 6 7 8 9 10
2 7
3 9
1 10

输出 #1

2 3 1

说明/提示

对于 的数据，，。

思路： 这很明显是一道静态区间多次查询问题，可以用ST表，记录i到i+2^k的最小账目数值。 具体代码如下：

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<deque>
#include<cmath>
#include<unordered_map>
using namespace std;
int m=0,n=0;
const int Max_n=1e5+5,Max_k=20;
int st_min[Max_k][Max_n]={},st_min_index[Max_k][Max_n]={}; 
int log_table[Max_n]={};

int readint(){	//快速读入 
	char ch=getchar();
	int x=0;
	while(ch<'0' || ch>'9') ch=getchar();
	while(ch>='0' && ch<='9'){
		x=(x<<3)+(x<<1)+(ch^48);
		ch=getchar();
	}
	return x;
}

void init_log(){	//对log2表进行预处理 
	log_table[1]=0;
	for(int i=2;i<=n;i++){
		log_table[i]=log_table[i/2]+1;
	}
}

int main(){
	n=readint();m=readint();
	for(int i=1;i<=n;i++){
		st_min[0][i]=readint();
		st_min_index[0][i]=i;
	} 
	init_log();	//对log2表进行预处理
	for(int k=1;k<Max_k;k++)
		for(int i=1;i+(1<<k)-1<=n;i++) st_min[k][i]=min(st_min[k-1][i],st_min[k-1][i+(1<<(k-1))]);
	
	while(m--){
		int a=readint(),b=readint();
		int k=log_table[b-a+1];
		int ans=min(st_min[k][a],st_min[k][b-(1<<k)+1]);	//查询最小值
		printf("%d ",ans);
	}
	return 0;
}