Cod sursa(job #217128)

Utilizator slayer4uVictor Popescu slayer4u Data 27 octombrie 2008 10:15:17
Problema Arbori de intervale Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include <stdio.h>

long n, i, init[1001], type, m, t[1001], x[1001], a, b;

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

void update(long p, long val)
{
	t[p] = val;
	p /= 2;

	for (; p; p /= 2)
		t[p] = max(t[p * 2], t[p * 2 + 1]);

}

void cstr (long st, long dr, long p)
{
	if (st == dr)
	{
		init[st] = p;
		return;
	}

	long mid = (st + dr) / 2;
	cstr(st, mid, 2 * p);
	cstr(mid + 1, dr, 2 * p + 1);
}

long query (long p, long a, long b, long aa, long bb)
{
	if (aa <= a  && b <= bb)
		return t[p];
	long mid = (a + b) / 2, rez = -2147000000;

	if (aa <= mid)
		rez = max(rez, query(2 * p, a, mid, aa, bb));


	if (bb > mid)
		rez = max(rez, query(2 * p + 1, mid + 1, b, aa, bb));

		return rez;
}

int main()
{
	freopen ("arbint.in", "rt", stdin);
	freopen ("arbint.out", "wt", stdout);

	scanf("%ld %ld", &n, &m);
	cstr(1, n, 1);
	for (i = 1; i <= n; ++i)
	{
		scanf("%ld", &x[i]);
		update(init[i], x[i]);
	}

	for (i = 1; i <= m; ++i)
	{
		scanf("%ld %ld %ld", &type, &a, &b);
		if (!type)
			printf("%ld\n", query(1, 1, n, a, b));
		else
			update(init[a], b);
	}

	return 0;
}