Cod sursa(job #945696)

Utilizator OpportunityVlad Negura Opportunity Data 2 mai 2013 17:21:37
Problema Arbori de intervale Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include <fstream>
#include <iostream>
using namespace std;
ifstream fi("arbint.in");
ofstream fo("arbint.out");

#define nmax 100001

long op,st,dr,x,n,m,i,t[nmax];

void add(long nod,long st,long dr,long v, long p){
	//cout << "n=" << nod << " s=" << st << " d=" << dr << " v=" << v << " p=" << p << endl;
	long mid=(st+dr)/2;
	if (st==dr) t[nod]=v; else{
		if (p<=mid) add(nod*2,st,mid,v,p);
		else add(nod*2+1,mid+1,dr,v,p);
		t[nod]=max(t[nod*2],t[nod*2+1]);
	}
}


long get(long nod,long st,long dr,long a,long b){
	long mid=(st+dr)/2,r1=0,r2=0;
	if (a<=st && b>=dr) return t[nod]; else{
		if (a<=mid) r1=get(nod*2,st,mid,a,b);
		if (b>mid) r2=get(nod*2+1,mid+1,dr,a,b);
		return max(r1,r2);
	}
}

int main(){
	
	fi >> n >> m;
	for (i=1; i<=n; i++){
		fi >> x;
		add(1,1,n,x,i);
		//for (long j=1; j<=2*n+1; j++) cout << t[j] << ' '; cout << endl;
	}
	
//	for (i=1; i<=2*n+1; i++) cout << t[i] << ' '; cout << endl;
	
	while (m--){
	//	cout << m << endl;
		fi >> op >> st >> dr;
		if (op) add(1,1,n,dr,st);
		else fo << get(1,1,n,st,dr) << endl;
	}
	
	return 0;
}