单点修改,区间查最值
题意
给定$n$个点,每次要么查询区间$[l, r]$的最大值,要么修改某个点的值。(同样是模板题,注意输入是多组测试数据)
#include <iostream>
#define lc u << 1
#define rc u << 1 | 1
using namespace std;
const int N = 200010;
int w[N];
int n, m;
struct Node{
int l, r;
int v;
}tr[N * 4];
void pushup (int u) { tr[u].v = max(tr[lc].v, tr[rc].v); }
void build (int u, int l, int r)
{
tr[u] = {l, r};
if (l == r) { tr[u].v = w[l]; return; }
int mid = l + r >> 1;
build (lc, l, mid), build (rc, mid + 1, r);
pushup(u);
}
void modify (int u, int x, int c)
{
if (tr[u].l == x && tr[u].r == x) tr[u].v = c;
else
{
int mid = tr[u].l + tr[u].r >> 1;
if (x <= mid) modify (lc, x, c);
else modify (rc, x, c);
pushup(u);
}
}
int query (int u, int l, int r)
{
if (tr[u].l >= l && tr[u].r <= r) return tr[u].v;
int mid = tr[u].l + tr[u].r >> 1;
int v = 0;
if (l <= mid) v = query (lc, l, r);
if (r > mid) v = max(v, query(rc, l, r));
return v;
}
void solve()
{
for (int i = 1; i <= n; i++) cin >> w[i];
build (1, 1, n);
while (m--)
{
char op[2];
int l, r;
cin >> op >> l >> r;
if (*op == 'Q') cout << query(1, l, r) << endl;
else modify(1, l, r);
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int T = 1;
// cin >> T;
// for(int turn = 1 ; turn <= T ; turn++)
while (cin >> n >> m) solve();
}