List Removals

Explicación

Cada consulta nos pide quitar el elemento en una posición dada de lo que actualmente queda en la lista.

El enfoque naive sería desplazar los elementos del arreglo después de cada eliminación, lo que cuesta $O(n)$ por consulta, lo que no alcanza aquí dadas las restricciones. Necesitamos una estructura de datos que soporte tanto consultas del k-ésimo elemento como eliminaciones de forma eficiente.

Las tres soluciones de abajo procesan cada consulta en $O(\log n)$ o $O(\log^2 n)$ , dando $O(n \log n)$ o $O(n\log^2 n)$ en total.

Solución 1 - Indexed Set

Guardamos los índices originales de todos los elementos que todavía están presentes en un indexed set. Esta estructura de datos builtin de C++ puede procesar consultas de la forma “quitar el elemento en la posición $p$ ”, y también puede acceder al índice original en una posición en tiempo $O(\log n)$ usando find_by_order.

C++


#include <bits/stdc++.h>
using namespace std;
 
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
 
template <class T>
using OrderedSet =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
int main() {
	int n;
	cin >> n;
 
	vector<int> values(n);
	for (int i = 0; i < n; i++) cin >> values[i];
 
	// Guardar los índices originales 0..n-1 de los elementos que todavía están
	OrderedSet<int> remaining_indices;
	for (int i = 0; i < n; i++) remaining_indices.insert(i);
 
	for (int i = 0; i < n; i++) {
		int query_pos;
		cin >> query_pos;
		query_pos--;  // 1-indexed → 0-indexed
 
		// el k-ésimo más chico en remaining_indices = índice original del k-ésimo elemento
		int original_idx = *remaining_indices.find_by_order(query_pos);
		remaining_indices.erase(original_idx);
		cout << values[original_idx] << " \n"[i == n - 1];
	}
}

Solución 2 - Búsqueda binaria sobre BIT

Mantenemos un Árbol de Fenwick (BIT) donde cada posición se inicializa en 1 (presente) y se pone en 0 cuando se elimina. La suma de prefijos prefix_sum(i) entonces cuenta cuántos elementos siguen presentes en las posiciones $1$ a $i$ .

Para hallar el índice original del $k$ -ésimo elemento restante, buscamos de forma binaria el índice más chico donde prefix_sum(index) == k. Cada paso de la búsqueda binaria hace una consulta al BIT, dando $O(\log^2 n)$ por operación.

C++


#include <bits/stdc++.h>
using namespace std;
 
int n;
 
// BeginCodeSnip{BIT Code (from PURS 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
 
// Búsqueda binaria del índice más chico donde prefix_sum == target
int find_kth(int target, BIT<int> &bit) {
	int lo = 1, hi = n;
	while (lo < hi) {
		int mid = (lo + hi) / 2;
		if (bit.pref_sum(mid) >= target) hi = mid;
		else lo = mid + 1;
	}
	return lo;
}
 
int main() {
 
	cin >> n;
 
	vector<int> values(n + 1);
	BIT<int> bit(n + 1);
 
	for (int i = 1; i <= n; i++) cin >> values[i];
	for (int i = 1; i <= n; i++) bit.add(i, 1);
 
	for (int q = 0; q < n; q++) {
		int query_pos;
		cin >> query_pos;
		int original_idx = find_kth(query_pos, bit);
		cout << values[original_idx] << " \n"[q == n - 1];
		bit.add(original_idx, -1);
	}
}

Solución 3 - Árbol de Segmentos

Construimos un Árbol de Segmentos donde cada nodo guarda la cantidad de elementos presentes en su rango. Para hallar el $k$ -ésimo elemento restante, caminamos hacia abajo en el árbol de la siguiente forma: si el hijo izquierdo contiene $\geq k$ elementos, recurrimos a la izquierda; si no, restamos el conteo del hijo izquierdo de $k$ y recurrimos a la derecha.

Esto halla la respuesta en $O(\log n)$ descendiendo exactamente un camino de raíz a hoja.

C++


#include <bits/stdc++.h>
 
using namespace std;
 
// BeginCodeSnip{Segment Tree}
template <class T> class SumSegmentTree {
  private:
	const T DEFAULT = 0;
 
	int len;
	vector<T> segtree;
 
	T combine(const T &a, const T &b) { return a + b; }
 
	void build(const vector<T> &arr, int at, int at_left, int at_right) {
		if (at_left == at_right) {
			segtree[at] = arr[at_left];
			return;
		}
		int mid = (at_left + at_right) / 2;
		build(arr, 2 * at, at_left, mid);
		build(arr, 2 * at + 1, mid + 1, at_right);
		segtree[at] = combine(segtree[2 * at], segtree[2 * at + 1]);
	}
 
	int remove_kth(int at, int at_left, int at_right, int k) {
		segtree[at]--;
		if (at_left == at_right) return at_left;
		int mid = (at_left + at_right) / 2;
		if (segtree[2 * at] >= k) return remove_kth(2 * at, at_left, mid, k);
		else return remove_kth(2 * at + 1, mid + 1, at_right, k - segtree[2 * at]);
	}
 
  public:
	SumSegmentTree(int len) : len(len) { segtree = vector<T>(len * 4, DEFAULT); };
 
	SumSegmentTree(const vector<T> &arr) : len(arr.size()) {
		segtree = vector<T>(len * 4, DEFAULT);
		build(arr, 1, 1, len);
	}
 
	int remove_kth(int pos) { return remove_kth(1, 1, len, pos); }
};
// EndCodeSnip
 
int main() {
	int n;
	cin >> n;
 
	vector<int> values(n + 1);
	for (int i = 1; i <= n; i++) cin >> values[i];
	SumSegmentTree<int> seg(vector<int>(n + 1, 1));
 
	for (int q = 0; q < n; q++) {
		int query_pos;
		cin >> query_pos;
		int original_idx = seg.remove_kth(query_pos);
		cout << values[original_idx] << " \n"[q == n - 1];
	}
}