NYOJ 1185-最大最小值【线段树：模板--学习ing】

系统管理员 2022-08-21 11:57 124阅读 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

来源

[原创][Link 1]

#include<stdio.h>
    #define INF 0x3f3f3f3f
    int maxtree[300300],mintree[300300];
    int max(int a,int b)
    {
    	return a>b?a:b;
    }
    int min(int a,int b)
    {
    	return a<b?a:b;
    }
    void build(int rt,int l,int r)
    {
    	int tp;
    	if(l==r)
    	{
    		scanf("%d",&tp);
    		mintree[rt]=maxtree[rt]=tp;
    		return;
    	}
    	int mid=(l+r)>>1;
    	tp=rt<<1;
    	build(tp,l,mid);build(tp|1,mid+1,r);
    	mintree[rt]=min(mintree[tp],mintree[tp|1]);
    	maxtree[rt]=max(maxtree[tp],maxtree[tp|1]); 
    } 
    int findmin(int rt,int l,int r,int a,int b)
    {
    	if(a<=l&&r<=b)
    	{
    		return mintree[rt];
    	}
    	int mid=(l+r)>>1,tp=rt<<1,res=INF;
    	if(mid>=b)
    	{
    		res=min(findmin(tp,l,mid,a,b),res);
    	}
    	else if(mid<a)
    	{
    		res=min(findmin(tp|1,mid+1,r,a,b),res);
    	}
    	else
    	{
    		res=min(findmin(tp,l,mid,a,b),res);
    		res=min(findmin(tp|1,mid+1,r,a,b),res);
    	}
    	return res;
    }
    int findmax(int rt,int l,int r,int a,int b)
    {
    	if(a<=l&&r<=b)
    	{
    		return maxtree[rt];
    	}
    	int mid=(l+r)>>1,tp=rt<<1,res=-INF;
    	if(mid>=b)
    	{
    		res=max(findmax(tp,l,mid,a,b),res);
    	}
    	else if(mid<a)
    	{
    		res=max(findmax(tp|1,mid+1,r,a,b),res);
    	}
    	else
    	{
    		res=max(findmax(tp,l,mid,a,b),res);
    		res=max(findmax(tp|1,mid+1,r,a,b),res);
    	}
    	return res;
    }
    int main()
    {
    	int t,a,b;
    	scanf("%d",&t);
    	while(t--)
    	{
    		int n,m;
    		scanf("%d",&n);
    		build(1,1,n);
    		scanf("%d",&m);
    		while(m--)
    		{
    			int ka;
    			scanf("%d%d%d",&ka,&a,&b);
    			if(ka==1)
    			{
    				printf("%d\n",findmin(1,1,n,a,b));
    			}
    			else if(ka==2)
    			{
    				printf("%d\n",findmax(1,1,n,a,b));
    			}
    			else
    			{
    				printf("%d\n",findmin(1,1,n,a,b)+findmax(1,1,n,a,b));
    			}
    		}
    	}
    	return 0;
    }

[Link 1]: http://acm.nyist.net/JudgeOnline/search_result.php?source=%E5%8E%9F%E5%88%9B