nyoj1185最大最小值(线段树)

网友投稿 235 2022-09-17

nyoj1185最大最小值(线段树)

​​​​

这道题普通方法 ,TLE。

最大最小值

1000 ms  |  内存限制: 65535

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 #include #define N 10005using namespace std;struct node { int left,right,min,max;}c[N*4];int a[N];void buildtree(int l,int r,int root){ c[root].left=l; c[root].right=r; if(l==r) { c[root].min=c[root].max=a[l]; return ; } int mid=(l+r)/2; buildtree(l,mid,root*2); buildtree(mid+1,r,root*2+1); c[root].min=min(c[root*2].min,c[root*2+1].min); c[root].max=max(c[root*2].max,c[root*2+1].max);}void findtree(int l,int r,int root,int &min1,int &max1){ if(c[root].left==l&&c[root].right==r) { min1=c[root].min; max1=c[root].max; return ; } int mid=(c[root].left+c[root].right)/2; if(mid=r) findtree(l,r,root*2,min1,max1); else { int min2,max2; findtree(l,mid,root*2,min1,max1); findtree(mid+1,r,root*2+1,min2,max2); min1=min(min1,min2); max1=max(max1,max2); }}int main(){ int t,n,x,l,r,sum,m,min1,max1; scanf("%d",&t); while(t--) { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); buildtree(1,n,1); scanf("%d",&m); while(m--) { scanf("%d %d %d",&x,&l,&r); findtree(l,r,1,min1,max1); if(x==1) printf("%d\n",min1); if(x==2) printf("%d\n",max1); if(x==3) printf("%d\n",min1+max1); } } return 0;}

版权声明:本文内容由网络用户投稿,版权归原作者所有,本站不拥有其著作权,亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容,请联系我们jiasou666@gmail.com 处理,核实后本网站将在24小时内删除侵权内容。

上一篇:nyoj304节能(区间dp)
下一篇:nyoj 38 布线问题(最小生成树 kruskal算法)
相关文章

 发表评论

暂时没有评论,来抢沙发吧~