Count the Trains

Análisis oficial (C++) 

Explicación

Sea $a_i$ la velocidad máxima del vagón $i$, y $v_i$ la velocidad a la que corre actualmente. Como el vagón $i$ nunca puede adelantar a los vagones que tiene delante, $v_i$ es el mínimo de prefijos $v_i = \min(a_1, \ldots, a_i)$. El arreglo $v_i$ es no creciente, y cada cambio de valor es un límite entre trenes. Así, en cualquier momento, la respuesta es el número de valores distintos en $v$.

En lugar de guardar todo el arreglo de mínimos de prefijos, mantenemos un conjunto de índices de inicio, o los índices donde empieza un tren nuevo, que son el índice $0$ y cada índice $i$ donde $v_i < v_{i-1}$. Observemos que $a_j = v_j$ en cualquier índice de inicio $j$, así que la velocidad verdadera de una posición $k$ es $a_j$, donde $j$ es el índice de inicio más cercano a la izquierda de $k$.

Cuando una consulta disminuye $a_k$, ocurre una de las siguientes:

• La velocidad verdadera $v_k$, definida por un índice de inicio, es igual o más lenta que $a_k$. Así, el conjunto de índices de inicio (es decir, el número de trenes) permanece igual.
• La velocidad verdadera anterior $v_k$ es mayor que $a_k$, lo que hace que $k$ se convierta en un índice de inicio. Observemos que que $k$ se convierta en un índice de inicio puede hacer que algunos índices de inicio queden obsoletos. Para eliminar estos índices obsoletos, comprobamos de forma iterativa el índice de inicio más cercano a la derecha de $k$, y vemos si su valor es mayor que $a_k$. Si es así, lo borramos y seguimos comprobando índices.

En cada momento, el número de trenes es igual al número de índices de inicio. Tenemos a lo sumo $\mathcal{O}(N+Q)$ inserciones de índices de inicio, y por lo tanto el número de eliminaciones de índices también está acotado por $\mathcal{O}(N+Q)$. Así, la complejidad temporal total se amortiza a $\mathcal{O}((N+Q) \log N)$.

Implementación

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

#include <bits/stdc++.h>
using namespace std;
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
 
	int test_num;
	cin >> test_num;
 
	for (int t = 0; t < test_num; ++t) {
		int n, q;
		cin >> n >> q;
 
		vector<long long> a(n);
		for (auto &x : a) { cin >> x; }
 
		// Construir el conjunto inicial de índices de inicio de tren
		vector<long long> pref_min(n);
		pref_min[0] = a[0];
		set<int> starts = {0};
 
		for (int i = 1; i < n; i++) {
			pref_min[i] = min(pref_min[i - 1], a[i]);
			if (pref_min[i] < pref_min[i - 1]) { starts.insert(i); }
		}
 
		while (q--) {
			int k;
			long long d;
			cin >> k >> d;
			k--;
 
			// El mayor índice de inicio <= k determina la velocidad verdadera actual del vagón k
			int j = *prev(starts.upper_bound(k));
			long long cur_speed = a[j];
 
			a[k] -= d;
 
			if (a[k] >= cur_speed) {
				cout << starts.size() << ' ';
				continue;
			}
 
			starts.insert(k);
 
			// Borrar todo índice de inicio posterior dominado por la nueva velocidad más baja
			auto it = next(starts.find(k));
			while (it != starts.end() && a[*it] >= a[k]) { it = starts.erase(it); }
 
			cout << starts.size() << ' ';
		}
 
		cout << '\n';
	}
}