蓝桥 晚会节目单 (线段树)

【问题描述】
小明要组织一台晚会，总共准备了 n 个节目。然后晚会的时间有限，他只能最终选择其中的 m 个节目。
这 n 个节目是按照小明设想的顺序给定的，顺序不能改变。
小明发现，观众对于晚会的喜欢程度与前几个节目的好看程度有非常大的关系，他希望选出的第一个节目尽可能好看，在此前提下希望第二个节目尽可能好看，依次类推。
小明给每个节目定义了一个好看值，请你帮助小明选择出 m 个节目，满足他的要求。
【输入格式】
输入的第一行包含两个整数 n, m ，表示节目的数量和要选择的数量。
第二行包含 n 个整数，依次为每个节目的好看值。
【输出格式】
输出一行包含 m 个整数，为选出的节目的好看值。
【样例输入】
5 3
3 1 2 5 4
【样例输出】
3 5 4
【样例说明】
选择了第1, 4, 5个节目。
【评测用例规模与约定】
对于 30% 的评测用例，1 <= n <= 20；
对于 60% 的评测用例，1 <= n <= 100；
对于所有评测用例，1 <= n <= 100000，0 <= 节目的好看值 <= 100000。

思路：每次选择最大的，并且顺序不能改变，==> 区间查询 ==> 线段树
好吧，说实话看同学的题解看了好久才弄明白，这就是要打acm的大佬和不打acm的菜鸡的差距。。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef struct{
   
    int l, r, id;
    int maxx;    //[l,r]最大值的下标 
}node;
node tree[400005];
int arr[100005];
int n, m;
void pushup(int cur){
   
    //tree[cur].val=tree[cur*2].val+tree[cur*2+1].val;
    if (tree[cur*2].maxx >= tree[cur*2+1].maxx){
   
        tree[cur].id=tree[cur*2].id;
        tree[cur].maxx=tree[cur*2].maxx;
    }else{
   
        tree[cur].id=tree[cur*2+1].id;
        tree[cur].maxx=tree[cur*2+1].maxx;
    }
}
void build(int cur, int l, int r){
   
    int mid=(l+r)/2;
    tree[cur].l=l, tree[cur].r=r;
    tree[cur].maxx=0;    //先初始化为0 
    if (l==r){
   
        tree[cur].maxx=arr[l];
        tree[cur].id=l;
    }
    else{
   
        build(cur*2, l, mid);
        build(cur*2+1, mid+1, r);
        pushup(cur);
    }
}
node query(int cur, int x, int y){
   
    int l=tree[cur].l, r=tree[cur].r;
    int mid=(l+r)/2;
    if (x<=l && r<=y){
   
        return tree[cur];
    }
    node t1, t2;
    if (x<=mid){
   
        t1=query(cur*2, x, y);
    }
    if (y>=mid+1){
   
        t2=query(cur*2+1, x, y); 
    }
    if (t1.maxx>t2.maxx)    return t1;
    else    return t2;
} 
int main(){
   
    scanf("%d%d", &n, &m);
    for (int i=1; i<=n; i++){
   
        scanf("%d", &arr[i]);
    }
    build(1, 1, n);
    int t=0;
    while (m--){
   
        //每次查询区间[t+1, n-m+1]的最大值
        node tnode=query(1, t+1, n-m+1);
        if (m!=0)    printf("%d ", tnode.maxx);
        else printf("%d", tnode.maxx);
        t=tnode.id;
    }
    return 0;
}