线段树优化做法

如果仔细读过题的话，就会发现这是一个静态的区间查询最大值与最小值。

很多人（如果你学过线段树的话）就会想到，我当年学线段树的例题不就是区间加，然后求区间最大值吗？何况还没有区间加这一操作，岂不嗨皮哉？？？

好的，看看数据范围。

1*10^6？？？

线段树能过的去吗？还需要维护两个值，不得两棵线段树吗？？？

这个问题就不难解决了：

首先是时间的问题。我们的常识告诉我们，O(nlogn)只能走100000，但是如果你的常数不是很大的话，单从线段树的时间复杂度上说，nlog₂n在n=1000000的话是1000000*20=20000000，加点常数还是可以过的。

接下来解决很多人总要写两棵线段树的问题。由上文知，20000000要求你的常数很小，而你如果写两棵线段树会增大你的常数，而且写起来费事，所以不如只写一棵线段树。

怎么写呢？？？

在此之前先了解一下我的宏定义QAQ，方便理解以下代码

#define root 1,n,1          //根节点的左右边界与节点编号#define lson l,m,rt<<1      //左儿子的左右边界与节点编号#define rson m+1,r,rt<<1|1  //右儿子的左右边界与节点编号

我们不妨写一个结构体

struct node{    int maxx,minn;//最大值与最小值}t, z[mn<<2];//t是用来接query函数（一会再讲）的返回值的             //z[]是用来存线段树主体的。

直接一起存，是不是省了两棵线段树的麻烦？

那么怎么更新呢？分别更新呗：

inline void update(int rt){//rt表示要更新的线段树节点    z[rt].maxx=max(z[rt<<1].maxx,z[rt<<1|1].maxx);    z[rt].minn=min(z[rt<<1].minn,z[rt<<1|1].minn);}

这样就可以更新当前节点啦！

我们的基础数值可以和建树操作一起进行。

inline void build(intl,int r,int rt){//建树    if(l==r){z[rt].minn=z[rt].maxx=read();}//这里一起进行（我用了个读入优化）    int m=(l+r)>>1;    build(lson);//左儿子    build(rson);//右儿子    update(rt);}

因为我们没有区间值的变化，所以就不写modify这部分了。接下来是一个查询的过程，这里有个细节，你要同时返回最小值与最大值，不能把左边和右边的一组答案直接作为这一个区间的答案，所以你只能把左右两边同时比较最大值最小值，最大值取两者中最大值最大，最小值取两者中最小值最小，然后合并成一个node结构体。

所以，为了简化这一步骤，可以多写一个函数：

inline node cmp(node a,node b){//函数名字就不要深究了    return (node){a.maxx > b.maxx ? a.maxx : b.maxx, a.minn < b.minn ? a.minn : b.minn};}

然后用在查询（query）函数中：

这里有个小小的优化：

如果你的判断是只有两个的话，这样会多次进入循环，所以可以直接从判断上省去一部分时间。

inline node query(int l,int r,int rt,int nowl,int nowr){    //变量分别是线段树左右端点，线段树节点编号，查询范围左右端点    if(nowl<=l && r<=nowr){return z[rt];}    int m=(l+r)>>1;    if(nowl<=m){        if(m

这样返回的就是区间的最大值和最小值了

主函数的部分直接在完整代码中详细讲解了

代码：

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
          
         
        
       
      
     
    

第九次写题解，希望可以帮到用线段树却惨遭TLE的同学