Cod sursa(job #591229)

Utilizator vladtarniceruVlad Tarniceru vladtarniceru Data 23 mai 2011 11:03:16
Problema Arbori de intervale Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
# include <fstream>
using namespace std;

ifstream f ("arbint.in");
ofstream g ("arbint.out");

int n, st, dr, i, m, H[300010], v[100003];

inline int maxim (int a, int b){
	if (a > b) return a;
	return b;
}

inline void update (int st, int dr, int node, int val, int poz){
	if (st >= dr){
		H[node] = val;
		return ;
	}
	
	int m = (st + dr) >> 1;
	
	if (poz <= m) 
		update (st, m, node << 1, val, poz);
	else
		update (m + 1, dr, (node << 1) + 1, val, poz);
	
	H[node] = maxim (H[node << 1], H[(node << 1) + 1]);
}

inline int query (int st, int dr, int i, int j, int node){
	if (i <= st && dr <= j) return H[node];
	
	int m = (st + dr) >> 1, sol = 0;
	
	if (i <= m) sol = maxim (sol, query (st, m, i, j, node << 1));
	if (m < j)  sol = maxim (sol, query (m + 1, dr, i, j, (node << 1) + 1));
	
	return sol;
}

int Q;

int main (){
	f >> n >> m;
	
	for (i = 1; i <= n; ++i){
		f >> v[i];
		update (1, n, 1, v[i], i);
	}
	
	for (; m > 0; --m){
		f >> Q >> st >> dr;
		
		if (!Q)
			g << query (1, n, st, dr, 1) << '\n';
		else
			update (1, n, 1, dr, st);
	}
	
	return 0;
}