最大最小值
时间限制：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#include<stdio.h>
#include<string.h>
#include<algorithm>
#define MAX 10010
using namespace std;
int Min[MAX<<2];
int Max[MAX<<2];
void pushup(int o)
{
Max[o]=max(Max[o<<1],Max[o<<1|1]);
Min[o]=min(Min[o<<1],Min[o<<1|1]);
}
void gettree(int o,int l,int r)
{
int a;
if(l==r)
{
scanf("%d",&a);
Max[o]=Min[o]=a;
return ;
}
int mid=(l+r)>>1;
gettree(o<<1,l,mid);
gettree(o<<1|1,mid+1,r);
pushup(o);
}
int find1(int o,int l,int r,int L,int R)
{
if(L<=l&&R>=r)
{
return Min[o];
}
int mid=(l+r)>>1;
int ans=MAX;
if(mid>=R)
ans=min(find1(o<<1,l,mid,L,R),ans);
else if(mid<L)
ans=min(find1(o<<1|1,mid+1,r,L,R),ans);
else
{
ans=min(find1(o<<1,l,mid,L,R),ans);
ans=min(find1(o<<1|1,mid+1,r,L,R),ans);
}
return ans;
}
int find2(int o,int l,int r,int L,int R)
{
if(L<=l&&R>=r)
return Max[o];
int mid=(l+r)>>1;
int ans=-100;
if(R<=mid)
ans=max(ans,find2(o<<1,l,mid,L,R));
else if(L>mid)
ans=max(ans,find2(o<<1|1,mid+1,r,L,R));
else
{
ans=max(ans,find2(o<<1,l,mid,L,R));
ans=max(ans,find2(o<<1|1,mid+1,r,L,R));
}
return ans;
}
int main()
{
int t,n,m,j,i;
int a,b,c;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
gettree(1,1,n);
scanf("%d",&m);
for(i=1;i<=m;i++)
{
scanf("%d%d%d",&a,&b,&c);
if(a==1)
{
printf("%d\n",find1(1,1,n,b,c));
}
if(a==2)
{
printf("%d\n",find2(1,1,n,b,c));
}
if(a==3)
{
printf("%d\n",find1(1,1,n,b,c)+find2(1,1,n,b,c));
}
}
}
return 0;
}