当前位置：网站首页>nyoj1185最大最小值（线段树）

nyoj1185最大最小值（线段树）

2022-08-05 11:02:00 【51CTO】

这道题普通方法，TLE。

最大最小值

1000 ms | 内存限制： 65535

给出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 <algorithm>
       
       #define N 10005
       
       using 
       
       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
       
       <
       
       l)
       
       findtree(
       
       l,
       
       r,
       
       root
       
       *
       
       2
       
       +
       
       1,
       
       min1,
       
       max1);
       
       else 
       
       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;
       
}
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.

原网站

版权声明
本文为[51CTO]所创，转载请带上原文链接，感谢
https://blog.51cto.com/u_15742657/5547121

当前位置：网站首页>nyoj1185最大最小值（线段树）

nyoj1185最大最小值（线段树）

最大最小值

边栏推荐

猜你喜欢

随机推荐