poj 1754 I Hate It 线段树

一时失言乱红尘 2022-06-08 08:13 162阅读 0赞

Problem Description  
很多学校流行一种比较的习惯。老师们很喜欢询问，从某某到某某当中，分数最高的是多少。  
这让很多学生很反感。

不管你喜不喜欢，现在需要你做的是，就是按照老师的要求，写一个程序，模拟老师的询问。当然，老师有时候需要更新某位同学的成绩。

Input  
本题目包含多组测试，请处理到文件结束。  
在每个测试的第一行，有两个正整数 N 和 M ( 0

#include<cstdio>
    #include<cstring> 
    #include<algorithm>
    using namespace std;
    #define maxn 1000000
    int a[maxn];  //保存值的数组 
    struct Node{
        int left, right;         //该节点维护的区间 
        int minvalue, maxvalue; //该节点保存的两个最值 
    }tree[4 * maxn];
    struct node{
        int minans, maxans;
    }ans[maxn];
    void build_tree(int le, int ri, int root){   //参数是区间的左值和右值，从根节 = 1点开始建树 
        tree[root].left = le;
        tree[root].right = ri;
        int mid = (le + ri) / 2;
        if(le == ri){
            tree[root].maxvalue = tree[root].minvalue = a[le];
            return ; 
        }
        build_tree(le, mid, root * 2);
        build_tree(mid + 1, ri, root * 2 + 1);
        tree[root].minvalue = min(tree[root * 2].minvalue, tree[root * 2 + 1].minvalue);
        tree[root].maxvalue = max(tree[root * 2].maxvalue, tree[root * 2 + 1].maxvalue);
    }
    int query(int le, int ri ,int root, int flag){       //falg是求最大值或者最小值的标志 
        if(tree[root].left == le && tree[root].right == ri){
            if(flag == 0)
                return tree[root].minvalue;
            else
                return tree[root].maxvalue;
        }
        int mid = (le + ri) / 2;
        if(mid >= ri)
            return query(le, ri, root * 2, flag);
        else if(mid < le)
            return query(le, ri, root * 2 + 1, flag);
        else{
            int valuele = query(le ,mid, root * 2, flag);
            int valueri = query(mid + 1, ri, root * 2 + 1, flag);
            if(flag == 0)
                return min(valuele, valueri);
            else
                return max(valuele, valueri);
        }   
    } 
    int main(){
        int n,m;  
        while(scanf("%d%d", &n, &m) != EOF){  
           for(int i = 1; i <= n; ++i)  
               scanf("%d", &a[i]);  
           build_tree(1, n, 1);  
    
           for(int i = 1; i <= n - m + 1; ++i){  
              int j = i + m - 1;  
              ans[i].minans = query(i,j,1,0);  
              ans[i].maxans = query(i,j,1,1);  
           }  
    
           for(int i = 1; i < n - m + 1; ++i)  
               printf("%d ",ans[i].minans);  
           printf("%d\n",ans[n-m+1].minans);  
    
           for(int i = 1; i < n - m + 1; ++i)  
               printf("%d ", ans[i].maxans);  
           printf("%d\n", ans[n-m+1].maxans);  
        }   
        return 0;
    }