nyoj 1185 最大最小值（线段树）

迈不过友情╰ 2024-02-17 21:12 65阅读 0赞

### 最大最小值 ###

时间限制： 1000 ms | 内存限制： 65535 KB

难度： 2

描述

给出N个整数，执行M次询问。

对于每次询问，首先输入三个整数C、L、R：

如果C等于1，输出第L个数到第R个数之间的最小值；

如果C等于2，输出第L个数到第R个数之间的最大值；

如果C等于3，输出第L个数到第R个数之间的最小值与最大值的和。

（包括第L个数和第R个数）。

输入

首先输入一个整数T（T≤100），表示有T组数据。  
对于每组数据，先输入一个整数N（1≤N≤10000），表示有N个整数；  
接下来一行有N个整数a（1≤a≤10000）；  
然后输入一个整数M，表示有M次询问；  
接下来有M行（1≤M≤10000），每行有3个整数C、L、R（1≤C≤3，1≤L≤R≤N）。

输出

按照题意描述输出。每个输出占一行。

样例输入

2
    4
    1 3 2 4
    2
    1 1 4
    2 2 3
    5
    1 2 3 4 5
    1
    3 1 5

样例输出

1
    3
    6

分析：这类题算是线段树类型题很简单的题目了吧，刚开始拿到这道题的时候，想的是二十多分钟可以a掉，然后敲了两个建树函数，两个查询函数，分分钟打脸，超时了；然后将两个建树函数浓缩成一个，还是超时……，然后把两个查询函数浓缩成一个，引用返回最大最小值，672ms过掉；总的来说这题多注意下就行了。

AC代码：

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    #define INF 1000000000
    const int maxn=1e4+10;
    int sum[maxn<<2];
    int sum2[maxn<<2];
    int a[maxn];
    int N;
    
    void build(int l,int r,int rt){
    	if(l==r){
    		sum[rt]=a[l];
    		sum2[rt]=a[l];
    		return ;
    	}
    	
    	int m=l+(r-l)/2;
    	build(l,m,rt<<1);
    	build(m+1,r,rt<<1|1);
    	
    	sum[rt]=min(sum[rt<<1],sum[rt<<1|1]);
    	sum2[rt]=max(sum2[rt<<1],sum2[rt<<1|1]);
    }
    
    void query(int i,int j,int l,int r,int rt,int& Min,int& Max){
    	if(i<=l && j>=r){
    		Min=min(Min,sum[rt]);
    		Max=max(Max,sum2[rt]);
    		return ;
    	}
    	
    	int m=l+(r-l)/2;
    	if(i<=m)
    	  query(i,j,l,m,rt<<1,Min,Max);
    	if(j>m)
    	  query(i,j,m+1,r,rt<<1|1,Min,Max);
    }
    
    int main(){
    	int T;
    	scanf("%d",&T);
    	while(T--){
    		scanf("%d",&N);
    		for(int i=1;i<=N;i++)
    		scanf("%d",&a[i]);
    		build(1,N,1);
    		
    		int M;
    		scanf("%d",&M);
    		for(int i=1;i<=M;i++){
    			int C,L,R;
    			scanf("%d%d%d",&C,&L,&R);
    			if(C==1){
    				int Max=0,Min=INF;
    				query(L,R,1,N,1,Min,Max);
    				printf("%d\n",Min);
    			}
    			else if(C==2){
    				int Max=0,Min=INF;
    				query(L,R,1,N,1,Min,Max);
    				printf("%d\n",Max);
    			}
    			else {
    				int Max=0,Min=INF;
    				query(L,R,1,N,1,Min,Max);
    				printf("%d\n",Max+Min);
    			}
    		}
    	}
    	return 0;
    }

。