Increasing Array Queries

¿Se puede primero idear un algoritmo para una sola consulta? No tiene que ser locamente eficiente; tiempo $\mathcal{O}(N)$ está bien.

Recorramos el arreglo en orden y llevemos la cuenta del elemento más grande $m$ que vimos hasta ahora. Para cada elemento $x$, primero actualizamos $m$. Luego, si el actual es menor que $m$, sumamos $m-x$ al total.

Como no podemos procesar cada consulta de esta forma, intentemos idear el concepto de una “contribución” de un cierto elemento.

Tomemos el arreglo $[10,4,11,3]$, por ejemplo. Pensemos cómo contribuyen $10$ y $11$ en particular a la respuesta.

Explicación

Preparación

Sigamos la línea de pensamiento de la Pista 2. Digamos que tenemos un elemento de valor $x$ en el índice $i$, y el siguiente elemento estrictamente mayor que $x$ está en el índice $j$. Si no hay un siguiente elemento mayor, sea $j$ uno más que el índice del último elemento.

La contribución de $x$ a una consulta sería la siguiente:

El segundo término es la suma de todos los elementos en el intervalo $[i,j)$.

Por ejemplo, en ese arreglo de la Pista 2, $10$ contribuye $10 \cdot (2-0)-(10+4)=6$, mientras que $11$ contribuye $11 \cdot (4-2)-(11+3)=8$ a la suma.

Notar que esto no aplica cuando el $j$ de un elemento se pasa del final de la consulta. Si solo consideráramos los primeros tres elementos del arreglo de la Pista 2, $11$ no contribuiría nada.

Ejecución

¿Cómo usamos esto?

Primero, tenemos que recorrer el arreglo en reversa.

También llevemos una pila de los valores e índices de todos los máximos que uno obtendría al recorrer desde un índice $i$ hasta el final del arreglo.

Tomemos de nuevo el arreglo de la Pista 2. Si estuviéramos en el índice $1$, nuestra pila sería $[(11, 2), (4, 1)]$, con el final del arreglo siendo el tope de la pila.

Cada elemento de esta pila contribuiría la cantidad dada por la fórmula de arriba a las respuestas de una consulta, dado que está completamente contenido dentro de dicha consulta.

Como los índices de la pila siempre son decrecientes, podemos usar una búsqueda binaria para hallar dónde queda la consulta dentro de la pila. Para el elemento de cola que podría no estar completamente contenido dentro de la consulta, podemos calcular la contribución a mano y sumarla al final.

Para actualizar de forma eficiente las contribuciones relativas a la pila, usaremos un Árbol de Fenwick (BIT). También necesitamos un arreglo de sumas de prefijos para calcular de forma eficiente el segundo término de esa fórmula de contribución.

Implementación

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

#include <algorithm>
#include <iostream>
#include <vector>
 
using std::cout;
using std::endl;
using std::pair;
using std::vector;
using ll = long long;
 
// BeginCodeSnip{BIT (from the module)}
template <class T> class BIT {
  private:
	int size;
	vector<T> bit;
	vector<T> arr;
 
  public:
	BIT(int size) : size(size), bit(size + 1), arr(size) {}
 
	void set(int ind, T val) { add(ind, val - arr[ind]); }
 
	void add(int ind, T val) {
		arr[ind] += val;
		ind++;
		for (; ind <= size; ind += ind & -ind) { bit[ind] += val; }
	}
 
	T pref_sum(int ind) {
		ind++;
		T total = 0;
		for (; ind > 0; ind -= ind & -ind) { total += bit[ind]; }
		return total;
	}
};
// EndCodeSnip
 
int main() {
	int arr_size;
	int query_num;
	std::cin >> arr_size >> query_num;
	vector<int> arr(arr_size);
	for (int &i : arr) { std::cin >> i; }
	vector<vector<pair<int, int>>> queries(arr_size);
	for (int q = 0; q < query_num; q++) {
		int start, end;
		std::cin >> start >> end;
		queries[start - 1].push_back({end - 1, q});
	}
 
	vector<ll> pref_arr(arr_size + 1);
	for (int i = 0; i < arr_size; i++) { pref_arr[i + 1] = pref_arr[i] + arr[i]; }
 
	vector<ll> ans(query_num);
	vector<pair<int, int>> maxes;
	BIT<ll> contrib(arr_size);
	for (int i = arr_size - 1; i >= 0; i--) {
		// actualizar nuestra pila
		while (!maxes.empty() && arr[i] >= maxes.back().first) {
			maxes.pop_back();
			// ya no contribuye nada: ponerlo en 0
			contrib.set(maxes.size(), 0);
		}
 
		// obtener la contribución de nuestro elemento nuevo
		int len = (maxes.empty() ? arr_size : maxes.back().second) - i;
		contrib.set(maxes.size(), (ll)arr[i] * len);
		maxes.push_back({arr[i], i});
 
		for (const auto &[end, q] : queries[i]) {
			// búsqueda binaria de dónde está el final de la consulta en la pila
			int lo = 0;
			int hi = maxes.size() - 1;
			int valid = -1;
			while (lo <= hi) {
				int mid = (lo + hi) / 2;
				if (maxes[mid].second <= end) {
					valid = mid;
					hi = mid - 1;
				} else {
					lo = mid + 1;
				}
			}
 
			// la contribución de la mayoría de los elementos máximos
			ll sum1 = contrib.pref_sum(maxes.size() - 1) - contrib.pref_sum(valid);
			// el elemento de cola mencionado en el editorial
			ll sum2 = (ll)(end - maxes[valid].second + 1) * maxes[valid].first;
			// el segundo término de la fórmula de contribución
			ll pref_sub = pref_arr[end + 1] - pref_arr[i];
			ans[q] = sum1 + sum2 - pref_sub;
		}
	}
 
	for (ll a : ans) { cout << a << '\n'; }
}