学步园

大意略。

线段树入门题。

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <string>
using namespace std;

const int maxn = 222222;
const int INF = 0x3f3f3f3f;

int max(int a, int b)
{
	return a > b? a : b;
}

int n, m;

int maxv[maxn*4];
int ql, qr;
int p, v;

void pushup(int o)
{
	maxv[o] = max(maxv[o*2], maxv[o*2+1]);
}

void build(int o, int L, int R)
{
	int M = L + (R-L)/2;
	if(L == R) scanf("%d", &maxv[o]);
	else
	{
		build(o*2, L, M);
		build(o*2+1, M+1, R);
		pushup(o);
	}
}

void update(int o, int L, int R)
{
	int M = L + (R-L)/2;
	if(L == R) maxv[o] = v;
	else
	{
		if(p <= M) update(o*2, L, M);
		else update(o*2+1, M+1, R);
		pushup(o);
	}
}

int query(int o, int L, int R)
{
	int M = L + (R-L)/2, ans = 0;
	if(ql <= L && R <= qr) return maxv[o];
	if(ql <= M) ans = max(ans, query(o*2, L, M));
	if(M < qr) ans = max(ans, query(o*2+1, M+1, R));
	return ans;
}

int main()
{
	while(~scanf("%d%d", &n, &m))
	{
		build(1, 1, n);
		while(m--)
		{
			char str[3];
			scanf("%s", &str);
			if(str[0] == 'Q')
			{
				scanf("%d%d", &ql, &qr);
				printf("%d\n", query(1, 1, n));
			}
			else
			{
				scanf("%d%d", &p, &v);
				update(1, 1, n);
			}
		}
	}
	return 0;
}