MEX vs MED

Pista

Para un subsegmento de longitud $\leq 2 \cdot \texttt{mex}$ , la condición $\texttt{mex} > \texttt{med}$ se satisface, ya que la mediana puede ser a lo sumo $\texttt{mex}-1$ .

Solución

Explicación

Análisis oficial

Iteraremos $\texttt{mex}$ de $1$ a $n-1$ , hallando todos los subsegmentos válidos de ese $\texttt{mex}$ a la vez.

Sean $l$ y $r$ la cota izquierda más alta y la cota derecha más baja, respectivamente, de un subsegmento que satisface un $\texttt{mex}$ dado, y $\texttt{pos}$ el índice de $\texttt{mex}$ . Si conocemos $l$ , $r$ y $\texttt{pos}$ , podemos contar rápidamente los subsegmentos para un $\texttt{mex}$ dado.

Necesitamos hallar todos los subsegmentos de longitud $\leq 2 \cdot \texttt{mex}$ que contienen $l \ldots r$ y omiten $\texttt{pos}$ . Primero, resolvamos para $\texttt{pos}>r$ . Iteremos $r$ hasta $\texttt{pos}-1$ , hallando todas las cotas de $l$ que satisfacen las restricciones para cada $r$ . Esto no es un problema de tiempo siempre que podamos hallar todos los valores posibles de $l$ en $\mathcal{O}(1)$ , ya que cada vez que iteramos aumentamos el tamaño del subsegmento en $1$ .

Considerando esta nueva cota de $r$ , podemos hallar el número de valores posibles de $l$ que forman un subsegmento válido hallando el número de posiciones $\leq l$ tales que $r-l+1 \leq \texttt{mex} \cdot 2$ . La cota inferior de nuestro menor valor de $l$ es $r-\texttt{mex} \cdot 2 + 1$ , que podemos hallar reordenando la desigualdad anterior.

Después de esto, sabemos que todos los valores entre $l$ y la cota inferior de $l$ son cotas izquierdas válidas para nuestro $r$ dado, así que podemos sumar $l-\texttt{smallest\\_l} + 1$ a la respuesta. Sin embargo, debemos considerar la cota inferior de $l$ como $0$ si es negativa, y no sumar $l-\texttt{smallest\\_l} + 1$ si es negativo.

Si $\texttt{pos} < l$ , podemos decrementar de $l$ a $\texttt{pos}+1$ , calculando todos los valores posibles de $r$ de forma similar.

Podemos guardar la posición de cada entero, lo que nos permite hallar la posición del siguiente $\texttt{mex}$ sin tener que buscar en el arreglo.

Implementación

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

C++JavaPython


#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
 
int main() {
	int test_num;
	cin >> test_num;
	for (int t = 0; t < test_num; t++) {
		int n;
		cin >> n;
 
		// guarda la posición de cada entero
		vector<int> pos(n);
 
		for (int i = 0; i < n; i++) {
			int x;
			cin >> x;
			pos[x] = i;
		}
 
		// inicializar cotas izquierda y derecha para mex
		int left = pos[0], right = pos[0];
		ll res = 1;
 
		// mex representa el mex actual que cubren left y right
		for (int mex = 1; mex < n; mex++) {
			int next_pos = pos[mex];
 
			// saltar si next_pos ya está entre left y right
			if (left <= next_pos && next_pos <= right) { continue; }
 
			// Como podemos crear un subsegmento válido para un mex dado hasta
			// tamaño mex * 2, nuestra diferencia máxima entre left y right es mex * 2 - 1.
			int max_diff = mex * 2 - 1;
 
			if (next_pos < left) {
				for (; left > next_pos; left--) {
					int largest_right = min(left + max_diff, n - 1);
					// sumar todas las cotas derechas posibles que no cambian el
					// mex actual
					res += max(largest_right - right + 1, 0);
				}
			} else {
				for (; right < next_pos; right++) {
					int smallest_left = max(right - max_diff, 0);
					// sumar todas las cotas izquierdas posibles que no cambian el
					// mex actual
					res += max(left - smallest_left + 1, 0);
				}
			}
		}
 
		cout << res << '\n';
	}
}


import java.io.*;
import java.util.*;
 
public class MAXvsMED {
	public static void main(String[] args) {
		Kattio io = new Kattio();
		int testNum = io.nextInt();
		for (int t = 0; t < testNum; t++) {
			int n = io.nextInt();
 
			// guarda la posición de cada entero
			int[] pos = new int[n];
			for (int i = 0; i < n; i++) {
				int x = io.nextInt();
				pos[x] = i;
			}
 
			// inicializar cotas izquierda y derecha para mex
			int left = pos[0], right = pos[0];
			long res = 1;
 
			// mex representa el mex actual que cubren left y right
			for (int mex = 1; mex < n; mex++) {
				int nextPos = pos[mex];
 
				// saltar si next_pos ya está entre left y right
				if (left <= nextPos && nextPos <= right) { continue; }
				// Como podemos crear un subsegmento válido para un mex dado hasta
				// tamaño mex * 2, nuestra diferencia máxima entre left y right es mex * 2 - 1
				int maxDiff = mex * 2 - 1;
 
				if (nextPos < left) {
					for (; left > nextPos; left--) {
						int largest_right = Math.min(left + maxDiff, n - 1);
						// sumar todas las cotas derechas posibles que no cambian el
						// mex actual
						res += Math.max(largest_right - right + 1, 0);
					}
				} else {
					for (; right < nextPos; right++) {
						int smallest_left = Math.max(right - maxDiff, 0);
						// sumar todas las cotas izquierdas posibles que no cambian el
						// mex actual
						res += Math.max(left - smallest_left + 1, 0);
					}
				}
			}
 
			io.println(res);
		}
 
		io.close();
	}
 
	// CodeSnip{Kattio}
}


for _ in range(int(input())):
	n = int(input())
 
	# guarda la posición de los enteros
	pos = [0] * n
 
	data = list(map(int, input().split()))
 
	for i in range(n):
		x = data[i]
		pos[x] = i
 
	# inicializar cotas izquierda y derecha para mex
	left = pos[0]
	right = pos[0]
	res = 1
 
	# mex representa el mex actual que cubren left y right
	for mex in range(1, n):
		next_pos = pos[mex]
 
		# Saltar si next_pos ya está entre left y right
		if left <= next_pos <= right:
			continue
 
		# Como podemos crear un subsegmento válido para un mex dado hasta
		# tamaño mex * 2, nuestra diferencia máxima entre left y right es mex * 2 - 1.
		max_diff = mex * 2 - 1
 
		if next_pos < left:
			while left > next_pos:
				largest_right = min(left + max_diff, n - 1)
 
				# Sumar todas las cotas derechas posibles que no cambian el mex actual
				res += max(largest_right - right + 1, 0)
				left -= 1
		else:
			while right < next_pos:
				smallest_left = max(right - max_diff, 0)
 
				# Sumar todas las cotas izquierdas posibles que no cambian el mex actual
				res += max(left - smallest_left + 1, 0)
				right += 1
 
	print(res)