2019 - Hedgehog Daniyar and Algorithms

Pista

El número de inversiones en un arreglo es el número de intercambios adyacentes que hay que hacer para ordenar un arreglo en orden no decreciente. ¿Cómo podemos usar esta idea para hallar el valor mínimo de $k$ requerido para ordenar el arreglo?

Explicación

En nuestro arreglo, solo hay que intercambiar elementos que son inversiones. Es decir, si tenemos un par $(i, j)$ donde $i < j$ y $w_i > w_j$ , entonces debemos intercambiarlos al ordenar el arreglo. Así, la respuesta es el máximo valor de $w_i + w_j$ entre todos los pares de inversión.

Para responder las consultas, barreemos de derecha a izquierda sobre el extremo izquierdo mientras mantenemos alguna estructura de datos para llevar el valor mínimo de $k$ para todos los extremos derechos. Una observación clave es que si en nuestro índice actual $i$ existe un $j$ donde $i < j$ y $w_i \leq w_j$ , entonces no podemos aumentar el valor de ningún par de inversión cuyo segundo valor tenga índice mayor que $j$ . Así, solo hay que actualizar los valores de los pares de inversión en el rango $[i + 1, j - 1]$ . Para hallar dicho valor de $j$ , usamos una pila monótona.

La forma más directa de resolver el problema a partir de aquí es usar un Árbol de Segmentos con propagación perezosa para llevar el mejor valor de par de inversión de cada índice (donde el valor de un par de inversión $(i, j)$ se guarda en el índice $j$ ) y el mejor valor de par de inversión en un rango. Para implementar esto, nótese que cada valor de par de inversión guardado en un índice $j$ es $w_j + x$ , donde $x$ es algún valor $w_i$ . Así, podemos usar una actualización de rango para aplicar el mejor valor de $x$ .

Nótese que también existe una solución más elegante (aunque menos intuitiva) con Árboles de Fenwick (BIT). Para esa solución, usamos un BIT para llevar el máximo de prefijo y lo actualizamos mientras extraemos elementos de nuestra pila monótona.

Implementación

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

C++


#include <bits/stdc++.h>
using namespace std;
 
// BeginCodeSnip{Lazy Segment Tree (from the module)}
template <class Info, class Tag> class LazySegtree {
  private:
	const int n;
	vector<Info> tree;
	vector<Tag> lazy;
 
	void build(int v, int l, int r, const vector<Info> &a) {
		if (l == r) {
			tree[v] = a[l];
		} else {
			int m = (l + r) >> 1;
			build(2 * v, l, m, a);
			build(2 * v + 1, m + 1, r, a);
			tree[v] = tree[2 * v] + tree[2 * v + 1];
		}
	}
 
	void apply(int v, int l, int r, const Tag &x) {
		tree[v].apply(x, l, r);
		lazy[v].apply(x);
	}
 
	void push_down(int v, int l, int r) {
		int m = (l + r) >> 1;
		apply(2 * v, l, m, lazy[v]);
		apply(2 * v + 1, m + 1, r, lazy[v]);
		lazy[v] = Tag();
	}
 
	void upd(int v, int l, int r, int ql, int qr, const Tag &x) {
		if (qr < l || ql > r) { return; }
		if (ql <= l && r <= qr) {
			apply(v, l, r, x);
		} else {
			push_down(v, l, r);
			int m = (l + r) >> 1;
			upd(2 * v, l, m, ql, qr, x);
			upd(2 * v + 1, m + 1, r, ql, qr, x);
			tree[v] = tree[2 * v] + tree[2 * v + 1];
		}
	}
 
	Info qry(int v, int l, int r, int ql, int qr) {
		if (qr < l || ql > r) { return Info(); }
		if (l >= ql && r <= qr) { return tree[v]; }
		push_down(v, l, r);
		int m = (l + r) >> 1;
		return qry(2 * v, l, m, ql, qr) + qry(2 * v + 1, m + 1, r, ql, qr);
	}
 
  public:
	LazySegtree(const vector<Info> &a) : n(a.size()) {
		tree.assign(4 << __lg(n), Info());
		lazy.assign(4 << __lg(n), Tag());
		build(1, 0, n - 1, a);
	}
 
	/** updates [ql, qr] with the arbitrary update chosen */
	void upd(int ql, int qr, const Tag &x) { upd(1, 0, n - 1, ql, qr, x); }
 
	/** @return result of range query on [ql, qr] */
	Info qry(int ql, int qr) { return qry(1, 0, n - 1, ql, qr); }
};
// EndCodeSnip
 
struct Tag {
	int added_val = -1;
	/** applies another lazy update to this update */
	void apply(const Tag &t) {
		if (t.added_val != -1) { added_val = t.added_val; }
	}
};
 
struct Info {
	int mx = -1;
	int applied = -1;
	/** applies an update to this tree node */
	void apply(const Tag &t, int l, int r) {
		if (t.added_val != -1) { applied = mx + t.added_val; }
	}
};
 
/** @return result of joining nodes a and b together */
Info operator+(const Info &a, const Info &b) {
	return {max(a.mx, b.mx), max(a.applied, b.applied)};
}
 
int main() {
	int n, q;
	cin >> n >> q;
	vector<int> w(n);
	for (int &i : w) { cin >> i; }
 
	vector<Info> arr(n);
	for (int i = 0; i < n; i++) {
		/*
		 * The default applied value (a.k.a. inversion pair value) must be
		 * initially set to 0, so that indices that aren't in an inversion pair
		 * will be effectively ignored by the segment tree.
		 */
		arr[i] = {w[i], 0};
	}
	LazySegtree<Info, Tag> st(arr);
 
	vector<vector<array<int, 3>>> tests(n);
	for (int i = 0; i < q; i++) {
		int l, r, k;
		cin >> l >> r >> k;
		l--, r--;
		tests[l].push_back({r, k, i});
	}
 
	vector<bool> res(q);
	stack<int> indices;
	for (int i = n - 1; i >= 0; i--) {
		// maintain a monotonic stack to find the first index j where w[i] >= w[j]
		while (!indices.empty() && w[indices.top()] < w[i]) { indices.pop(); }
		int b = indices.empty() ? n : indices.top();
		indices.push(i);
		st.upd(i + 1, b - 1, {w[i]});
		for (auto [r, k, idx] : tests[i]) { res[idx] = st.qry(i, r).applied <= k; }
	}
 
	for (int i = 0; i < q; i++) { cout << res[i] << '\n'; }
}