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 <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.