kuangbin_SegTree B (HDU 1754)
3686 ワード
A題と似ているのはupdateを増減から直接賦値queryに変更して求和から最大値を求めるだけで他はほとんど同じです
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
#define INF 0x3f3f3f3f
#define lson l, m, root<<1
#define rson m+1, r, root<<1|1
using namespace std;
const int MAXN = 2e5+10;
int val[MAXN*4];
void pushup(int root)
{
val[root] = max(val[root<<1], val[root<<1|1]);
}
void build(int l, int r, int root)
{
if(l == r) scanf("%d", &val[root]);
else{
int m = (l + r) >> 1;
build(lson);
build(rson);
pushup(root);
}
}
void update(int point, int value, int l, int r, int root)
{
if(l == r) val[root] = value;
else{
int m = (l + r) >> 1;
if(point <= m) update(point, value, lson);
else update(point, value, rson);
pushup(root);
}
}
int query(int L, int R, int l, int r, int root)
{
if(L <= l && R >= r) return val[root];
int res = 0;
int m = (l + r) >> 1;
if(L <= m) res = max(res, query(L, R, lson));
if(R > m) res = max(res, query(L, R, rson));
return res;
}
int main()
{
int n, m;
while(~scanf("%d%d", &n, &m)){
build(1, n, 1);
char op[2];
while(m--){
scanf("%s", op);
int u, v;
scanf("%d%d", &u, &v);
if(op[0] == 'U') update(u, v, 1, n, 1);
else{
if(u > v) swap(u, v);
printf("%d
", query(u, v, 1, n, 1));
}
}
}
return 0;
}