Skip to Content
CTRL K

Growing Trees

Análisis oficial 

Complejidad temporal: O(Nlog⁡N+Qlog⁡2N)\mathcal O(N\log N + Q\log^2 N)

Mantengamos un arreglo aa, que está ordenado por altura. Para responder una consulta de tipo C, podemos simplemente hacer búsqueda binaria sobre los extremos de la consulta.

Ahora, solo necesitamos soportar actualizaciones. Primero hagamos búsqueda binaria de la primera posición ll tal que a[l]≥ha[l] \geq h. Sea r=l+c−1r = l + c - 1. Solo hay que incrementar el rango [l,r][l, r] en 11 manteniendo aa ordenado.

Sin embargo, no podemos simplemente sumar 11 a todos los elementos del rango [l,r][l, r] porque esto podría romper el orden. Esto ocurre sii hay algún índice i∈[l,r]i\in [l, r] tal que a[i]=a[r+1]a[i] = a[r + 1]; si incrementamos el rango [l,r][l, r], entonces a[i]>a[r+1]a[i] > a[r + 1], que es una inversión.

Para evitar este error, hallamos otro rango [l′,r′][l', r'] tal que a[i]=a[r]a[i] = a[r] para todo i∈[l′,r′]i\in [l', r']; esto se puede hallar con búsqueda binaria. Como todos los j<ij < i satisfacen a[j]<a[i]a[j] < a[i], podemos incrementar [l,l′−1][l, l' - 1] primero. Luego, como hay que incrementar un total de cc elementos, nos quedan c−(l′−l)c - (l' - l) elementos. Incrementamos el rango [r′−(c−(l′−l))+1,r′][r' - (c - (l' - l)) + 1, r'] en uno.

Nótese que esto no crea inversiones porque a[r′+1]a[r' + 1] es mayor que a[r′]a[r'] antes de la actualización: después de la actualización, el arreglo quedaría no decreciente.

Las actualizaciones y consultas se pueden manejar con un árbol de segmentos perezoso, pero un árbol indexado binario alcanzaría ya que solo necesitamos consultas puntuales.

#include <bits/stdc++.h>
using namespace std;
 
#define N 100000
 
int n, q, a[N], bit[N];
 
void add(int l, int r, int x) {  // add x to [l, r]
	if (r < l) return;
	for (; l < n; l |= l + 1) bit[l] += x;
	for (++r; r < n; r |= r + 1) bit[r] -= x;
}
int query(int i) {  // point query at i
	int sum = 0;
	for (; i >= 0; i &= i + 1, --i) sum += bit[i];
	return sum;
}
/* from Benq */
template <class T, class U> T firstTrue(T lo, T hi, U f) {
	assert(lo <= hi);
	++hi;              // assuming f is increasing
	while (lo < hi) {  // find first index such that f is true
		T mid = lo + (hi - lo) / 2;
		f(mid) ? hi = mid : lo = mid + 1;
	}
	return lo;
}
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
 
	cin >> n >> q;
	for (int i = 0; i < n; ++i) cin >> a[i];
	sort(a, a + n);
	for (int i = 0; i < n; ++i) add(i, i, a[i]);
	for (int i = 0; i < q; ++i) {
		char c;
		int a, b;
 
		cin >> c >> a >> b;
		if (c == 'F') {
			int l = firstTrue(0, n - 1, [&](int i) { return query(i) >= b; });
			if (l == n)  // found nothing
				continue;
			int r = l + a - 1;
			if (r >= n - 1) {
				add(l, n - 1, 1);
				continue;
			}
			int x = query(r);
			int l_ = firstTrue(l, n - 1, [&](int i) { return query(i) >= x; });
			int r_ = firstTrue(l_, n - 1, [&](int i) { return query(i) > x; }) - 1;
			add(l, l_ - 1, 1);
			add(r_ - (a - (l_ - l)) + 1, r_, 1);
		} else {
			int l = firstTrue(0, n - 1, [&](int i) { return query(i) >= a; });
			int r = firstTrue(0, n - 1, [&](int i) { return query(i) > b; });
			cout << r - l << '\n';
		}
	}
}
Fundamentos