RMQ?ST表?没必要！线段树大法好。

题目描述

老管家是一个聪明能干的人。他为财主工作了整整10年，财主为了让自已账目更加清楚。要求管家每天记k次账，由于管家聪明能干，因而管家总是让财主十分满意。但是由于一些人的挑拨，财主还是对管家产生了怀疑。于是他决定用一种特别的方法来判断管家的忠诚，他把每次的账目按1，2，3…编号，然后不定时的问管家问题，问题是这样的：在a到b号账中最少的一笔是多少？为了让管家没时间作假他总是一次问多个问题。

输入输出格式

输入格式

输入中第一行有两个数m,n表示有m(m<=100000)笔账,n表示有n个问题，n<=100000。

第二行为m个数,分别是账目的钱数

后面n行分别是n个问题,每行有2个数字说明开始结束的账目编号。

输出格式

输出文件中为每个问题的答案。具体查看样例。

INPUT & OUTPUT’s examples

Input’s eg #1

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

Output’s eg #1

2 3 1

分析

看完题意，我们可以一眼就可以看出这是一个典型的RMQ问题。

~~所以当然要用ST表啦QAQ！~~

显然，ST表的RMQ查询仅需$O(1)$的时间，跑的贼快。但常常另辟蹊径（瞎搞乱搞）的$Herself32$认为，线段树是更好地解法。（~~实际上是因为他还没学会如何打ST表233~~）。

由于本题仅需维护一个最小值的查询，所以，在线段树的结构成员中，我们也仅需一个int型变量Min。

显然，我们在建树时就要维护查询，所以我们用线段树的左儿子节点和右儿子节点的最小值来更新它们的父亲。

建树过程其他部分与线段树模板一样。

建树完成之后，我们来写区间查询操作，区间查询的本质其实就是将原区间分成两部分，然后对每一个区间的目标区间进行查询。

那么现在就有几种情况了：

查询区间$[L,R]$在线段树区间$[l,mid]$以内，那么就返回Query(l,mid,L,R,LeftChild(k))。
查询区间$[L,R]$在线段树区间$[mid+1,r]$以内，那么就返回query(mid+1,r,ll,rr,lson)。
查询区间$[L,R]$一部分在线段树区间$[l,mid]$以内，另一部分在线段树区间$[mid+1,r]$以内，那么就返回min(Query(l,mid,L,mid,LeftChild(k)),Query(mid+1,r,mid+1,R,RightChild(k)))。

如此递归下去，最终直到达到边界，返回SegTree[k].Min。

代码

/* Headers */
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cctype>
#include<vector>
#include<iostream> 
using namespace std;
namespace FastIO{
    const int BUFSIZE=1<<20;
    char ibuf[BUFSIZE],*is=ibuf,*it=ibuf;
    char obuf[BUFSIZE],*os=obuf,*ot=obuf+BUFSIZE;
    inline char getch(){
        if(is==it)
            it=(is=ibuf)+fread(ibuf,1,BUFSIZE,stdin);
        return (is==it)?EOF:*is++;
    }
    inline int getint(){
        int res=0,neg=0,ch=getch();
        while(!(isdigit(ch)||ch=='-')&&ch!=EOF)
            ch=getch();
        if(ch=='-'){
            neg=1;ch=getch();
        }
        while(isdigit(ch)){
            res=(res<<3)+(res<<1)+(ch-'0');
            ch=getch();
        }
        return neg?-res:res;
    }
    inline void flush(){
        fwrite(obuf,1,os-obuf,stdout);
        os=obuf;
    }
    inline void putch(char ch){
        *os++=ch;
        if(os==ot)	flush();
    }
    inline void putint(int res){
        static char q[10];
        if(res==0)	putch('0');
        else if(res<0){
            putch('-');
            res=-res;
        } 
        int top=0;
        while(res){
            q[top++]=res%10+'0';
            res/=10;
        }
        while(top--)	putch(q[top]);
    }
} 
using namespace FastIO;
const int MAXN = 1e5+4;
/* definitions */
struct Node{
	int Min;
};
Node SegTree[MAXN<<2];
int n,m,cost[MAXN];
const int inf = 8798787978;
/* functions */
inline int LeftChild(int x){
	return x<<1;
}
inline int RightChild(int x){
	return (x<<1)+1;
}
inline void pushUp(int k){
	SegTree[k].Min=min(SegTree[LeftChild(k)].Min,SegTree[RightChild(k)].Min); 
}
inline void Build(int l,int r,int k){
	if(l==r){
		SegTree[k].Min=cost[l];
		return;
	}
	int mid=(l+r)>>1;
	Build(l,mid,LeftChild(k));
	Build(mid+1,r,RightChild(k));
	pushUp(k);
}
inline int Query(int l,int r,int L,int R,int k){
	if(l==L&&r==R)return SegTree[k].Min;
	int mid=(l+r)>>1;
	if(R<=mid)return Query(l,mid,L,R,LeftChild(k));
	else if(L>mid)return Query(mid+1,r,L,R,RightChild(k));
	else{
		return min(Query(l,mid,L,mid,LeftChild(k)),Query(mid+1,r,mid+1,R,RightChild(k)));
	}
}
int main(int argc,char *argv[]){
	scanf("%d%d",&n,&m);
	memset(SegTree,inf,sizeof(SegTree));
	for(int i=1;i<=n;i++){
		scanf("%d",&cost[i]);
	}
	Build(1,n,1);
	for(int i=1;i<=m;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		int ans=Query(1,n,x,y,1);
		printf("%d ",ans);
	}
	return 0;
}

洛谷P1816题解