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
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define Lson 2 * o, L, M        //左儿子，这样写减少了代码量，不易出错
#define Rson 2 * o + 1, M + 1, R    //ps：开始没有这样写，debug了好久
const int MAXM = 3 * 200000 + 10;   //结点总数应略小于区间长度的两倍，这里2*却TLE！
int maxV[MAXM], num[MAXM];
int ql, qr, p, v;
int n, m;
//向上更新，由 o 的左右儿子更新 o
void PushUp(int o)
{
    maxV[o] = max(maxV[2 * o], maxV[2 * o + 1]);
}
//建树
void Build(int o, int L, int R)
{
    if (L == R) maxV[o] = num[L]; //scanf("%d", &maxV[o]);   //叶子结点
    else
    {
        int M = (L + R) / 2;
        Build(Lson);            //左子树
        Build(Rson);            //右子树
        PushUp(o);              //更新
    }
}
//查询区间ql，qr最大值 o为当前结点编号，L为当前结点左端点，R为右端点
int Query(int o, int L, int R)
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX