线段树—效率至上

亦凉 2022-07-12 05:20 102阅读 0赞

think:  
1今天上午用了一个半小时完成了这个题目，这是自己做的第二个线段树的题目，因为一些自身的原因导致内心不断波动，无法投入高效率的学习状态，希望自己以后争取考虑事情全面一点，做一个有原则的懂礼貌的人，而不是盲目冲动，不要因为别的事情影响到自己的学习生活，学会把生活与学习作为两个独立的生命部分来对待，知错就改吧，自己的错误该道歉的就道歉，不要因为生活上的事情影响学习。现在回归正题，这个题目直观的提问是让我们判断某以区间的最大值与最小值的差值，如果直接建一个树的情况下考虑是否应该每一个子树不应该都用相同的边数相减记录最大值与最小值的差值，可能那样对思路的逻辑和严谨和专心效率要求会比较高，这个题目我是开了三个数组，通过一个数组记录输入的值，再通过这个数组分别建立一个最大树和一个最小树。最后用某一区间的最大树的最大值减去这个区间的最小树的最小值得到所求结果。  
2 本题目的线段树知识我用到的有：选取左右孩子的最大值/选取左右孩子的最小值/建树/在最大树中判断某一区间的最大值/在最小树中判断某一区间的最小值

[sdut原题链接][sdut]

效率至上  
Time Limit: 5000MS Memory Limit: 65536KB

Problem Description  
题意很简单,给出一个数目为n的非有序序列,然后有m次查询.对于每次查询输入两个正整数l,r请输出区间\[l,r\]的最大值与最小值的差值

Input  
第一行：输入两个正整数n,m (1<=n<=50000, 1<=m<=200000 )；  
第二行：输入n个整数 大小范围为\[1,100000\];  
接下来的m行,每次两个正整数l,r (1<=l<=r<=n);

Output  
输出区间\[l,r\]最大值与最小值的差值.

Example Input  
6 3  
1  
7  
3  
4  
2  
5  
1 5  
4 6  
2 2

Example Output  
6  
3  
0

Hint

Author

以下为accepted代码

#include <stdio.h>
    #define MAXN 200004
    #define Max(a, b) (a > b? a: b)
    #define Min(a, b) (a < b? a: b)
    int max[MAXN], min[MAXN], M[MAXN];
    void PushUpMax(int rt)//选择左右孩子中的最大值
    {
        max[rt] = Max(max[rt*2], max[rt*2+1]);
    }
    void PushUpMin(int rt)//选择左右孩子中的最小值
    {
        min[rt] = Min(min[rt*2], min[rt*2+1]);
    }
    void Build(int l, int r, int rt)//建树
    {
        if(l == r)
        {
            scanf("%d", &M[rt]);
            max[rt] = min[rt] = M[rt];
            return;
        }
        int m = (l + r)/2;
        Build(l, m, rt*2);
        Build(m+1, r, rt*2+1);
        PushUpMax(rt);//调用选择左右孩子最大值的函数
        PushUpMin(rt);//调用选择左右孩子最小值的函数
    }
    int FindMax(int L, int R, int l, int r, int rt)//寻找区间[L, R]的最大值
    {
        if(L <= l && r <= R)
        {
            return max[rt];
            //printf("max[%d]:%d\n", rt, max[rt]);
        }
        int  m = (l + r)/2, maxL = 0, maxR = 0;
        if(L <= m) maxL = FindMax(L, R, l, m, rt*2);
        if(R > m) maxR = FindMax(L, R, m+1, r, rt*2+1);
        return Max(maxL, maxR);
    }
    int FindMin(int L, int R, int l, int r, int rt)//寻找区间[L, R]的最小值
    {
        if(L <= l && r <= R)
        {
            return min[rt];
        }
        int m = (l + r)/2, minL = 100004, minR = 100004;
        if(L <= m) minL = FindMin(L, R, l, m, rt*2);
        if(R > m) minR = FindMin(L, R, m+1, r, rt*2+1);
        return Min(minL, minR);
    }
    int main()
    {
        int n, m, i, L, R;
        scanf("%d %d", &n, &m);
        Build(1, n, 1);//建树
        for(i = 0; i < m; i++)
        {
            scanf("%d %d", &L, &R);
            printf("%d\n", FindMax(L, R, 1, n, 1) - FindMin(L, R, 1, n, 1));//输出区间[L, R]的最大值与最小值之差
        }
        return 0;
    }
    
    
    /***************************************************
    User name: jk160630
    Result: Accepted
    Take time: 348ms
    Take Memory: 1544KB
    Submit time: 2017-02-13 09:54:24
    ****************************************************/

[sdut]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestproblem/cid/2009/pid/3302