Compras em FDL

fdl.cpp

// solucao de Frederico Bulhoes

#include <bits/stdc++.h>

#define LEFT ((no<<1)+1)
#define RIGHT ((no<<1)+2)

using namespace std;

const int maxn = 100010;

struct node
{
	int min, max;
};

node operator&(const node &l, const node &r)
{
	return {min(l.min, r.min),
	        max(l.max, r.max)};
}

int v[maxn];
node tree[maxn*4];

void build(int no, int l, int r)
{
	if (l == r) {

		tree[no] = {v[l], v[l]};
		return;
	}

	int m = (l+r)>>1;

	build(LEFT, l, m);
	build(RIGHT, m+1, r);

	tree[no] = tree[LEFT] & tree[RIGHT];
}

void upd(int no, int l, int r, int p, int val)
{
	if (l == r) {

		tree[no] = {val, val};
		return;
	}

	int m = (l+r)>>1;

	if (p <= m) upd(LEFT, l, m, p, val);
	else upd(RIGHT, m+1, r, p, val);

	tree[no] = tree[LEFT] & tree[RIGHT];
}

node get(int no, int l, int r, int a, int b)
{
	if (a <= l and r <= b) return tree[no];

	int m = (l+r)>>1;

	if (b <= m) return get(LEFT, l, m, a, b);
	if (a > m) return get(RIGHT, m+1, r, a, b);

	return get(LEFT, l, m, a, b) & get(RIGHT, m+1, r, a, b);
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int n;

	while (cin >> n) {

		for (int i = 1; i <= n; i++) cin >> v[i];

		build(0, 1, n);

		int q;
		cin >> q;

		while (q--) {

			int op;
			cin >> op;

			if (op == 1) {

				int p, val;
				cin >> p >> val;

				upd(0, 1, n, p, val);
			}
			else {

				int l, r;
				cin >> l >> r;

				node ans = get(0, 1, n, l, r);

				cout << ans.max-ans.min << "\n";
			}
		}
	}
}