Skip to Content
CTRL K

Editor

Análisis oficial 

Explicación

Sea lev[x]=max(0,-a[x]).

Sea active_y[x]=true si la operación x está activa después de y operaciones, y false en caso contrario. Obviamente active_y[y]=true.

Sea activepath_y[x]=true si la operación x podría deshacerse después de otra operación, y false en caso contrario. En otras palabras, active_y[x]=true y no existe un z>x con active_y[z]=true y lev[z]<=lev[x]. Si este es el caso, diremos que “x está en el camino activo de y.” Obviamente, activepath_y[y]=true.

Afirmación: Si activepath_y[x] entonces active_y[1..x]=active_x[1..x].

Demostración: Usamos inducción. Supongamos que esto es cierto para y=1..q y queremos demostrarlo para y=q+1. Si lev[q+1]=0 entonces q+1 es el único vértice en el camino activo de q+1, así que esto vale de forma obvia. En caso contrario, supongamos que la operación q+1 deshace la operación z en el camino activo de q. Por la hipótesis inductiva, active_q[1..z]=active_z[1..z], lo cual implica que active_{q+1}[1..z-1]=active_{z-1}[1..z-1].

Todas las operaciones en el camino activo de q+1 aparte de q+1 misma también están en el camino activo de z-1. Además, para cualquier t en el camino activo de z-1, active_t[1..t]=active_{z-1}[1..t]=active_{q+1}[1..t]. Esto completa la demostración.

Así, la solución es mantener el camino activo para cada i. Si existe una operación de nivel 0 en el camino activo de i, entonces su estado es la respuesta para i; en caso contrario, la respuesta para i es 0.

Implementación

Complejidad temporal: O(Nlog⁡N)\mathcal O(N \log N).

#include <cassert>
#include <iostream>
 
const int MAX_N = 3e5 + 1;
const int MAX_D = 19;  // ceil(log2(3*(10^5)))
 
int state[MAX_N], par[MAX_N][MAX_D], lev[MAX_N];
 
/** get last op on active path of x with lev <= max_lev */
int get_par(int x, int max_lev) {
	if (lev[x] <= max_lev) { return x; }
	for (int i = MAX_D - 1; i >= 0; i--) {
		if (lev[par[x][i]] > max_lev) { x = par[x][i]; }
	}
	return par[x][0];
}
 
int main() {
	int n;
	std::cin >> n;
	for (int i = 1; i <= n; i++) {
		std::cin >> state[i];
		if (state[i] < 0) {
			lev[i] = -state[i];
			int z = get_par(i - 1, lev[i] - 1);
			assert(z);  // must be something to undo
			par[i][0] = get_par(z - 1, lev[i] - 1);
 
			// levels of ops in active path are strictly decreasing
			assert(lev[i] > lev[par[i][0]]);
 
			for (int j = 1; j < MAX_D; j++) {
				par[i][j] = par[par[i][j - 1]][j - 1];  // prepare binary jumps
			}
		}
		std::cout << state[get_par(i, 0)] << '\n';
		// current active path is i, par[i], par[par[i]], ...
	}
}
import math
 
MAX_N = 300001
MAX_D = math.ceil(math.log2(MAX_N))
 
state = [0] * MAX_N
par = [[0] * MAX_D for _ in range(MAX_N)]
lev = [0] * MAX_N
 
 
def get_par(x: int, max_lev: int) -> int:
	"""get last op on active path of x with lev <= max_lev"""
	if lev[x] <= max_lev:
		return x
	for i in range(MAX_D - 1, -1, -1):
		if lev[par[x][i]] > max_lev:
			x = par[x][i]
	return par[x][0]
 
 
n = int(input())
 
for i in range(1, n + 1):
	state[i] = int(input())
 
	if state[i] < 0:
		lev[i] = -state[i]
		z = get_par(i - 1, lev[i] - 1)
 
		# must be something to undo
		assert z > 0
 
		par[i][0] = get_par(z - 1, lev[i] - 1)
 
		# levels of ops in active path are strictly decreasing
		assert lev[i] > lev[par[i][0]]
 
		# prepare binary jumps
		for j in range(1, MAX_D):
			par[i][j] = par[par[i][j - 1]][j - 1]
 
	# current active path is i, par[i], par[par[i]], ...
	print(state[get_par(i, 0)])
Fundamentos