2005 - Mountain

Solución con Árbol de Segmentos disperso

Este problema se puede resolver con un Árbol de Segmentos disperso. Llevamos el máximo de prefijo y la suma de rango en cada nodo, y caminamos sobre el Árbol de Segmentos para responder las consultas. La implementación de abajo usa punteros, pero es posible escribir la solución sin usarlos.

Complejidad temporal: $\mathcal{O}(Q\log{N})$

C++


#include <bits/stdc++.h>
using namespace std;
 
class SparseSegtree {
  private:
	const int n;
	struct Node {
		// vals = {prefix max, range sum}
		array<int, 2> vals = {0, 0};
		int lazy_set = INT32_MAX;
		Node *left = nullptr;
		Node *right = nullptr;
	};
	Node *root = new Node;
 
	array<int, 2> comb(const array<int, 2> &a, const array<int, 2> &b) {
		return {max(a[0], a[1] + b[0]), a[1] + b[1]};
	}
 
	void apply(Node *cur, int len, int val) {
		(cur->vals)[1] = len * val;
		(cur->vals)[0] = max(0, len * val);
		(cur->lazy_set) = val;
	}
 
	void push_down(Node *cur, int l, int r) {
		if ((cur->left) == nullptr) { (cur->left) = new Node; }
		if ((cur->right) == nullptr) { (cur->right) = new Node; }
		if (l != r && (cur->lazy_set) != INT32_MAX) {
			int m = (l + r) / 2;
			apply(cur->left, m - l + 1, cur->lazy_set);
			apply(cur->right, r - m, cur->lazy_set);
		}
		(cur->lazy_set) = INT32_MAX;
	}
 
	void range_set(Node *cur, int l, int r, int ql, int qr, int val) {
		if (qr < l || ql > r) { return; }
		if (ql <= l && r <= qr) {
			apply(cur, r - l + 1, val);
		} else {
			push_down(cur, l, r);
			int m = (l + r) / 2;
			range_set(cur->left, l, m, ql, qr, val);
			range_set(cur->right, m + 1, r, ql, qr, val);
			(cur->vals) = comb((cur->left)->vals, (cur->right)->vals);
		}
	}
 
	int walk_right(Node *cur, int l, int r, const array<int, 2> &pf, int mx) {
		if (l == r) {
			return l;
		} else {
			push_down(cur, l, r);
			int m = (l + r) / 2;
			array<int, 2> x = comb(pf, (cur->left)->vals);
			return x[0] > mx ? walk_right(cur->left, l, m, pf, mx)
			                 : walk_right(cur->right, m + 1, r, x, mx);
		}
	}
 
  public:
	SparseSegtree(int n) : n(n) {}
 
	void range_set(int ql, int qr, int val) { range_set(root, 0, n - 1, ql, qr, val); }
 
	int walk_right(int mx) { return walk_right(root, 0, n - 1, {0, 0}, mx); }
};
 
int main() {
	int n;
	cin >> n;
	SparseSegtree st(n + 2);
 
	while (true) {
		char type;
		cin >> type;
		if (type == 'I') {
			int a, b, d;
			cin >> a >> b >> d;
			st.range_set(a, b, d);
		} else if (type == 'Q') {
			int height;
			cin >> height;
			cout << st.walk_right(height) - 1 << "\n";
		} else if (type == 'E') {
			break;
		}
	}
}

Solución con compresión de coordenadas

Consideremos una versión más fácil del problema donde $N \leq 10^{6}$ . En ese caso, usamos un Árbol de Segmentos de suma máxima de prefijo con actualizaciones perezosas. Luego, para hallar el último índice donde la suma máxima de prefijo $\leq H$ , caminamos sobre el Árbol de Segmentos.

Sin embargo, $N \leq 10^{9}$ , lo que invalida el enfoque de arriba. El enfoque que describiré abajo no utiliza un Árbol de Segmentos disperso.

Dado que no necesitamos responder las consultas online, podemos comprimir coordenadas de los valores. Entonces, cada índice del Árbol de Segmentos representa un rango, en lugar de ser una ubicación individual. Digamos que tenemos actualizaciones de rango sobre los siguientes subarreglos:

[1, 10], [2, 5]

Entonces, podemos mantener los siguientes valores distintos:

[1, 2, 6, 11]

Estos valores distintos definen los rangos $[1, 2], [2, 5], [6, 10]$ . Entonces, si queremos actualizar el rango $[1, 10]$ , podemos actualizar los tres subrangos listados arriba. La idea es que si mantenemos un arreglo $vals[i]$ , entonces cada índice $i$ representará el rango $[vals[i], vals[i + 1] - 1]$ . Para cada actualización sobre el rango $[a, b]$ , el arreglo $vals$ debería contener $a$ y $b + 1$ .

Después de resolver la compresión de coordenadas, la mayor parte del Árbol de Segmentos es bastante similar al enfoque descrito al principio.

Implementación

Complejidad temporal: $\mathcal{O}(Q\log{Q})$

C++


#include <bits/stdc++.h>
using namespace std;
 
class LazySegtree {
  private:
	static constexpr array<int, 3> ID = {0, 0, 0};
	static constexpr int LZ_ID = INT32_MAX;
	const int sz;
 
	vector<array<int, 3>> t;
	vector<int> lz, vals;
 
	/** @return result of joining two ranges together */
	array<int, 3> comb(const array<int, 3> &a, const array<int, 3> &b) {
		return {max(a[0], a[1] + b[0]), a[1] + b[1], a[2] + b[2]};
	}
 
	/** builds the segment tree nodes */
	void build(int v, int l, int r) {
		if (l == r) t[v] = {0, 0, vals[l + 1] - vals[l]};
		else {
			int m = (l + r) / 2;
			build(2 * v, l, m);
			build(2 * v + 1, m + 1, r);
			t[v] = comb(t[2 * v], t[2 * v + 1]);
		}
	}
 
	/** applies the update to node v and places the lazy update */
	void apply(int v, int x) {
		int full_sub = t[v][2] * x;
		if (x >= 0) {
			t[v] = {full_sub, full_sub, t[v][2]};
		} else {
			t[v] = {0, full_sub, t[v][2]};
		}
		lz[v] = x;
	}
 
	/** pushes down the lazy update on node v to its children */
	void push_down(int v, int l, int r) {
		if (lz[v] != LZ_ID && l != r) {
			apply(2 * v, lz[v]);
			apply(2 * v + 1, lz[v]);
		}
		lz[v] = LZ_ID;
	}
 
	void range_set(int v, int tl, int tr, int ql, int qr, int amt) {
		if (qr < tl || ql > tr) return;
		if (ql <= tl && tr <= qr) {
			apply(v, amt);
		} else {
			push_down(v, tl, tr);
			int m = (tl + tr) / 2;
			range_set(2 * v, tl, m, ql, qr, amt);
			range_set(2 * v + 1, m + 1, tr, ql, qr, amt);
			t[v] = comb(t[2 * v], t[2 * v + 1]);
		}
	}
 
	int walk_right(int v, int l, int r, array<int, 3> cur, int mx) {
		if (l == r) {
			/*
			 * r is the first index where adding it causes the prefix max to be
			 * > mx. To find the first point after the previous range where
			 * prefix max <= mx, we need to do a bit of math.
			 */
			int dx = mx - cur[1];
			int div = t[v][1] / t[v][2];
			return vals[l] - 1 + dx / div;
		} else {
			int m = (l + r) / 2;
			push_down(v, l, r);
			/*
			 * We need to keep track of our current prefix's result,
			 * so every time we walk right, we need to join the left
			 * child's tree node to our prefix result.
			 */
			array<int, 3> x = comb(cur, t[v * 2]);
			return x[0] > mx ? walk_right(2 * v, l, m, cur, mx)
			                 : walk_right(2 * v + 1, m + 1, r, x, mx);
		}
	}
 
  public:
	LazySegtree(const vector<int> &arr)
	    : sz((int)arr.size() - 1), t(4 * sz, ID), lz(4 * sz, LZ_ID), vals(arr) {
		build(1, 0, sz - 1);
	}
 
	/** sets the range [ql, qr] (coordinate compressed indexes) to amt */
	void range_set(int ql, int qr, int amt) { range_set(1, 0, sz - 1, ql, qr, amt); }
 
	/** @return the last location where the height <= mx */
	int walk_right(int mx) { return walk_right(1, 0, sz - 1, ID, mx); }
 
	/** @return largest prefix sum in the whole array */
	int best_prefix() { return t[1][0]; }
};
 
int main() {
	int n;
	cin >> n;
	vector<vector<int>> tests;
	vector<int> vals = {0};
	while (true) {
		char type;
		cin >> type;
		if (type == 'I') {
			int a, b, d;
			cin >> a >> b >> d;
			tests.push_back({0, a, b, d});
			vals.push_back(a);
			vals.push_back(b + 1);
		} else if (type == 'Q') {
			int h;
			cin >> h;
			tests.push_back({1, h});
		} else {
			break;
		}
	}
 
	sort(begin(vals), end(vals));
	vals.erase(unique(begin(vals), end(vals)), end(vals));
	const auto id = [&](int x) -> int {
		return lower_bound(begin(vals), end(vals), x) - begin(vals);
	};
 
	LazySegtree st(vals);
	for (const vector<int> &cur : tests) {
		if (cur[0] == 0) {
			st.range_set(id(cur[1]), id(cur[2] + 1) - 1, cur[3]);
		} else {
			cout << (st.best_prefix() <= cur[1] ? n : st.walk_right(cur[1])) << "\n";
		}
	}
}