C++ 解法, 执行用时: 117ms, 内存消耗: 3320K, 提交时间: 2021-05-23 00:10:34

#include <stdio.h>
#include <algorithm>
#define MN 200000

int n,m,mn[MN*4+5],mx[MN*4+5];

void modify(int k,int l,int r,int p,int w){
	if(l==r){
		mn[k] = mx[k] = w;
		return;
	}
	int mid = (l+r)>>1;
	if(p<=mid) modify(k<<1,l,mid,p,w);
	else modify(k<<1|1,mid+1,r,p,w);
	mn[k] = std::min(mn[k<<1],mn[k<<1|1]);
	mx[k] = std::max(mx[k<<1],mx[k<<1|1]);
}

int qmin(int k,int l,int r,int L,int R){
	if(l==L&&r==R) return mn[k];
	int mid = (l+r)>>1;
	if(R<=mid) return qmin(k<<1,l,mid,L,R);
	if(L>mid) return qmin(k<<1|1,mid+1,r,L,R);
	return std::min(qmin(k<<1,l,mid,L,mid),qmin(k<<1|1,mid+1,r,mid+1,R));
}

int qmax(int k,int l,int r,int L,int R){
	if(l==L&&r==R) return mx[k];
	int mid = (l+r)>>1;
	if(R<=mid) return qmax(k<<1,l,mid,L,R);
	if(L>mid) return qmax(k<<1|1,mid+1,r,L,R);
	return std::max(qmax(k<<1,l,mid,L,mid),qmax(k<<1|1,mid+1,r,mid+1,R));
}

int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		int a;
		scanf("%d",&a);
		modify(1,1,n,a,i);
	}
	while(m--){
		int l,r;
		scanf("%d%d",&l,&r);
		printf("%d %d\n",qmin(1,1,n,l,r),qmax(1,1,n,l,r));
	}
}