题目描述
题目思路
- 维护当前结点的最大值
- 向序列后添加一个数，相当于将最后一个数修改为某数
- 询问这个序列中最后L个数中最大的数是多少，相当于求两个子结点的最大值
题目代码
#include
#include
#include
#include
using namespace std;
typedef long long LL;
const int N = 200010;
int m, p;
struct Node
{
int l, r;
int v; // 区间[l, r]中的最大值
}tr[N * 4];
void pushup(int u) // 由子节点的信息，来计算父节点的信息
{
tr[u].v = max(tr[u << 1].v, tr[u << 1 | 1].v);
}
void build(int u, int l, int r)
{
tr[u] = {l, r};
if(l == r) return;
int mid = l + r >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
}
int query(int u, int l, int r)
{
if(tr[u].l >= l && tr[u].r > 1;
int v = 0;
if (l mid) v = max(v, query(u << 1 | 1, l, r));
return v;
}
void modify(int u, int x, int v) // 将x对应结点最大值改为v
{
if(tr[u].l == x && tr[u].r == x) tr[u].v = v;
else
{
int mid = tr[u].l + tr[u].r >> 1;
if(x
Original: https://www.cnblogs.com/esico/p/16534757.html
Author: esico
Title: AcWing 1275. 最大数（线段树）
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/619895/
转载文章受原作者版权保护。转载请注明原作者出处！