Cards

Complejidad temporal: $\mathcal O(N\log N)$

Explicación

Podemos usar un Árbol de Segmentos para resolver este problema.

Para cada nodo del Árbol de Segmentos con el rango $[l, r]$, guardamos si es posible disponer las cartas $l\dots r$ de modo que

• no volvamos la carta $l$ ni la carta $r$
• no volvamos la carta $l$ y sí volvamos la carta $r$
• volvamos la carta $l$ y no volvamos la carta $r$
• volvamos la carta $l$ y la carta $r$

Podemos representar estos estados en una matriz 2 por 2 bool[2][2] donde la primera dimensión guarda si volvemos la carta $l$ y la segunda dimensión guarda si volvemos la carta $r$.

Para calcular los estados de un nodo concreto del Árbol de Segmentos, recorremos todos los estados posibles de nuestro nodo hijo izquierdo $(a, b)$ y todos los estados posibles de nuestro nodo hijo derecho $(c, d)$. Si la transición de $b$ a $c$ funciona, entonces $(a, d)$ funciona, ya que solo consideramos los extremos.

Para realizar una operación de intercambio con índices $i$ y $j$, simplemente intercambiamos las cartas en $i$ y $j$. Podemos recalcular todos los nodos del Árbol de Segmentos que están relacionados con $i$ o con $j$. Como hay alrededor de $\mathcal O(\log N)$ rangos en el Árbol de Segmentos que contienen a $i$ o a $j$, toda esta operación de intercambio toma $\mathcal O(\log N)$.

Además, también tenemos que imprimir si podemos formar una lista no decreciente usando las cartas. Para ello, si alguno de los estados del nodo raíz de nuestro Árbol de Segmentos (que cubre $[1, n]$) es posible, entonces la respuesta es sí (TAK); en caso contrario, no (NIE).

Implementación

#include <bits/stdc++.h>
using namespace std;
 
const int N = 1 << 18;
 
int n, q, aa[N][2];
bool tt[N << 1][2][2];
 
void pull(int i, int l, int r) {
	memset(tt[i], 0, sizeof(tt[i]));
	int j = i << 1, k = i << 1 | 1;
	int m = (l + r) >> 1;
	for (int a = 0; a < 2; ++a)
		for (int b = 0; b < 2; ++b)
			for (int c = 0; c < 2; ++c)
				for (int d = 0; d < 2; ++d)
					if (tt[j][a][b] && tt[k][c][d] && aa[m][b] <= aa[m + 1][c])
						tt[i][a][d] = 1;
}
 
void build(int k = 1, int l = 0, int r = n - 1) {
	if (l == r) {
		tt[k][0][0] = tt[k][1][1] = 1;
		return;
	}
	int m = (l + r) >> 1;
	build(k << 1, l, m);
	build(k << 1 | 1, m + 1, r);
	pull(k, l, r);
}
 
void update(int i, int k = 1, int l = 0, int r = n - 1) {
	if (l == r) {
		tt[k][0][0] = tt[k][1][1] = 1;
		return;
	}
	int m = (l + r) >> 1;
	if (i <= m) update(i, k << 1, l, m);
	else update(i, k << 1 | 1, m + 1, r);
	pull(k, l, r);
}
 
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; ++i) { scanf("%d%d", aa[i], aa[i] + 1); }
	build();
	scanf("%d", &q);
	while (q--) {
		int i, j;
		scanf("%d%d", &i, &j);
		swap(aa[--i], aa[--j]);
		update(i), update(j);
		bool ok = tt[1][0][0] || tt[1][0][1] || tt[1][1][0] || tt[1][1][1];
		printf("%s\n", ok ? "TAK" : "NIE");
	}
}

Solución alternativa

Podemos reducir el número de estados guardados en el Árbol de Segmentos a solo dos:

• El menor valor final del intervalo dado que tomamos el lado menor de la primera carta (denotamos esto como $FF$)
• El menor valor final del intervalo dado que tomamos el lado mayor de la primera carta (denotamos esto como $SS$)

Notemos que siempre será óptimo tomar el lado menor del último lado siempre que podamos tomar ambos. Esto, a su vez, prepara el intervalo actual para el siguiente paso de fusión, si aplica.

Denotemos el arreglo de cartas como $A$, donde $A.FF$ es el lado frontal y $A.SS$ es el lado posterior. Sin pérdida de generalidad, supongamos que $A[i].FF \leq A[i].SS$ para todo $i \in [1, n]$. Consideramos fusionar el intervalo $u$ y $v$ para crear el intervalo $w$, donde $w$ corresponde a los elementos del arreglo $[l, r]$. Notemos que esto implica que $u$ corresponde a $[l, m]$ y $v$ corresponde a $[m + 1, r]$, donde $m = \lfloor \frac {l + r} 2 \rfloor$

• $$w.FF = \begin{cases} v.FF & u.FF \leq A[m + 1].FF \\ v.SS & A[tm + 1].FF < u.FF \leq A[tm + 1].SS \\ \infty & \text{otherwise}\end{cases}$$
• $$w.SS = \begin{cases} v.FF & u.SS \leq A[m + 1].FF \\ v.SS & A[tm + 1].FF < u.SS \leq A[tm + 1].SS \\ \infty & \text{otherwise}\end{cases}$$

Notemos que elegimos $\infty$ como valor por defecto, porque bajo nuestras condiciones de fusión, el infinito anula convenientemente a todos los demás operadores. Esto significa que si algún punto del arreglo es discontinuo (o no se puede convertir en una secuencia no decreciente), el nodo $1$ del Árbol de Segmentos, que corresponde a todo el arreglo, también tendrá $w.FF = w.SS = \infty$.

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

Implementación

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
using pll = pair<ll, ll>;
 
#define MP make_pair
#define FF first
#define SS second
 
const ll llinf = 999999999999999;
 
ll N, Q;
pll A[200005], T[800005];
 
void merge(int t, int tl, int tr) {
	T[t] = MP(llinf, llinf);
	int tm = (tl + tr) >> 1;
	// for first val
	if (T[t << 1].FF <= A[tm + 1].SS) T[t].FF = T[t << 1 | 1].SS;
	if (T[t << 1].FF <= A[tm + 1].FF) T[t].FF = T[t << 1 | 1].FF;
	// for second val
	if (T[t << 1].SS <= A[tm + 1].SS) T[t].SS = T[t << 1 | 1].SS;
	if (T[t << 1].SS <= A[tm + 1].FF) T[t].SS = T[t << 1 | 1].FF;
}
 
void build(ll t = 1, ll tl = 1, ll tr = N) {
	T[t] = MP(llinf, llinf);
	if (tl == tr) {
		T[t] = A[tl];
		return;
	}
	ll tm = (tl + tr) >> 1;
	build(t << 1, tl, tm);
	build(t << 1 | 1, tm + 1, tr);
	merge(t, tl, tr);
}
 
void update(int i, pll v, int t = 1, int tl = 1, int tr = N) {
	if (tl == tr) {
		T[t] = A[tl] = v;
		return;
	}
	ll tm = (tl + tr) >> 1;
	if (i <= tm) update(i, v, t << 1, tl, tm);
	else update(i, v, t << 1 | 1, tm + 1, tr);
	merge(t, tl, tr);
}
 
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
 
	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> A[i].FF >> A[i].SS;
		if (A[i].FF > A[i].SS) swap(A[i].FF, A[i].SS);
	}
	build();
	cin >> Q;
	while (Q--) {
		int a, b;
		cin >> a >> b;
		pll t = A[a];
		update(a, A[b]);
		update(b, t);
		if (T[1].FF == llinf) cout << "NIE\n";
		else cout << "TAK\n";
	}
}