Cod sursa(job #616582)

Utilizator cipri_tomCiprian Tomoiaga cipri_tom Data 12 octombrie 2011 21:28:38
Problema Arbori de intervale Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include <fstream>
#include <utility>
using namespace std;

#define DIM 100001

ifstream fin("arbint.in");
ofstream fout("arbint.out");

int M, N;
int a[DIM], arb[DIM];

int start, finish, val, pos, maxim;

void Update(int nod, int st, int dr);
void Querry (int nod, int st, int dr);

int main()
{
	fin >> M >> N;
	for ( int i = 1; i <= N; ++i )
	{
		fin >> a[i];
		pos = i;
		val = a[i];
		Update(1, 1, N);
	}

	int r, x, y;
	for ( int i = 1; i <= M; ++i )
	{
		fin >> r >> x >> y;
		if ( r )
		{
			pos = x;
			val = y;
			Update(1, 1, N);
		}
		else
		{
			maxim = -1;
			start = x, finish = y;
			Querry(1, 1, N);
			fout << maxim << '\n';
		}
	}

	return 0;
}

void Update ( int nod, int st, int dr )
{
	if ( st == dr )
	{
		arb[nod] = val;
		return;
	}
	int mij = (st + dr) / 2;
	if ( pos <= mij )
		Update(2*nod, st, mij);
	else
		Update(2*nod + 1, mij + 1, dr);

	arb[nod] = max ( arb[2 * nod], arb[2 * nod + 1] );
}

void Querry(int nod, int st, int dr)
{
	if ( start <= st and dr <= finish )
	{
		if ( maxim < arb[nod] )
			maxim = arb[nod];
		return;
	}
	int mij = (st + dr) / 2;
	if ( start <= mij )
		Querry(2*nod, st, mij);
	if ( mij < finish )
		Querry ( 2 * nod + 1, mij + 1, dr);
}