Cod sursa(job #898458)

Utilizator cprogrammer1994Cprogrammer cprogrammer1994 Data 28 februarie 2013 10:22:14
Problema Arbori de intervale Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.5 kb
#include <cstring>
#include <cstdio>
#include <cmath>

int * array[18];
int size[18];

void change(int i, int v) {
	array[0][i] = v;
	for (int k = 1; k < 18; ++k) {
		i = i / 2;
		int a = array[k - 1][i * 2 + 0];
		int b = array[k - 1][i * 2 + 1];
		array[k][i] = a > b ? a : b;
	}
}

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

int maxim(int k, int l, int r) {
	if (l == r) {
		return(array[k][l]);
	}
	if (l % 2) {
		return(max(array[k][l], maxim(k, l + 1, r)));
	} else {
		if (r % 2) {
			return(maxim(k + 1, l / 2, r / 2));
		} else {
			return(max(array[k][r], maxim(k, l, r - 1)));
		}
	}
}

int main() {
	FILE * in = fopen("arbint.in", "rt");
	FILE * out = fopen("arbint.out", "wt");

	size[0] = 1 << 17;
	for (int k = 1; k < 18; ++k) {
		size[k] = size[k - 1] / 2 + size[k - 1] % 2;
	}
	for (int k = 0; k < 18; ++k) {
		array[k] = new int[size[k]];
	}

	int n, m;
	fscanf(in, "%d%d", &n, &m);
	for (int i = 0; i < n; ++i) {
		fscanf(in, "%d", &array[0][i]);
	}

	int size = n;
	for (int k = 1; k < 18; ++k) {
		size = size / 2 + size % 2;
		for (int i = 0; i < size; ++i) {
			int a = array[k - 1][i * 2 + 0];
			int b = array[k - 1][i * 2 + 1];
			array[k][i] = a > b ? a : b;
		}
		if (size % 2) {
			array[k][size] = 0;
		}
	}

	for (int i = 0; i < m; ++i) {
		int t, x, y;
		fscanf(in, "%d%d%d", &t, &x, &y);
		if (t) {
			change(x - 1, y);
		} else {
			fprintf(out, "%d\n", maxim(0, x - 1, y - 1));
		}
	}

	fclose(in);
	fclose(out);
}