Cod sursa(job #2421968)

Utilizator theoioanaUCV STOICA DANCIULESCU BLEOANCA theoioana Data 16 mai 2019 20:46:12
Problema Arbori de intervale Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.8 kb
#include <iostream>
#include <algorithm>
#include <fstream>
#define left_child (nod * 2)
#define right_child (left_child | 1)

using namespace std;

#define cin fin
#define cout fout
 
ifstream fin("aint.in");
ofstream fout("aint.out");
int aint[4 * 100005];

int vec[100005];

void build_tree(int nod, int left_limit, int right_limit) {

	if (left_limit == right_limit) {
		aint[nod] = vec[right_limit];
		return;
	}

	int mid = (left_limit + right_limit) / 2;

	build_tree(left_child, left_limit, mid);
	build_tree(right_child, mid + 1, right_limit);
	
	aint[nod] = max(aint[left_child], aint[right_child]);
}

int query_tree(int nod, int left_limit, int right_limit, int my_left, int my_right) {

	if (my_left <= left_limit && my_right >= right_limit) {
		return aint[nod];
	}

	int mid = (left_limit + right_limit) / 2;

	int res = 0;

	if (my_left <= mid) res = max(res, query_tree(left_child, left_limit, mid, my_left, my_right));
	if (my_right > mid) res = max(res, query_tree(right_child, mid + 1, right_limit, my_left, my_right));

	return res;
}

void update_tree(int nod, int left_limit, int right_limit, int pos, int value) {

	if (left_limit == right_limit && right_limit == pos) {
		aint[nod] = value;
		return;
	}

	int mid = (left_limit + right_limit) / 2;

	if (pos <= mid) update_tree(left_child , left_limit, mid, pos, value);
	else update_tree(right_child, mid + 1, right_limit, pos, value);

	aint[nod] = max(aint[left_child], aint[right_child]);
}

int main() {

	int n, m;

	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		cin >> vec[i];
	}

	build_tree(1, 0, n - 1);

	while (m--) {
		int o, a, b;

		cin >> o >> a >> b;

		if (o == 0) cout << query_tree(1, 0, n - 1, a - 1, b - 1) << endl;
		else update_tree(1, 0, n - 1, a - 1, b);
	}

}