Suitable Edit for LIS

Análisis oficial 

Explicación

Podemos resolver este problema con la técnica de LIS con Árbol de Segmentos.

Si la solución óptima contiene una actualización en el índice $i$, actualizaremos $A_i$ a $A_{i-1}+1$ si $i>1$ y a $0$ en caso contrario. Si tenemos alguna subsecuencia creciente que contiene el valor $A_{i-1}$ y queremos agregar un nuevo elemento justo después de $A_{i-1}$, es óptimo elegir $A_{i-1}+1$. Esto se debe a que maximiza la cantidad de opciones para el siguiente elemento mientras sigue siendo $>A_{i-1}$. Siempre es óptimo actualizar $A_i$ a $A_{i-1}+1$ porque si $A_{i-1}+1$ sigue directamente a $A_{i-1}$, no debemos tomar ningún índice entre el índice de $A_{i-1}$ y $A_{i-1}+1$. Actualizar el valor en el índice $i$ a $A_{i-1}+1$ hace que el $A_i$ original sea el único valor que no podemos tomar. Si actualizamos el valor en un índice posterior, no podremos tomar un conjunto más grande de valores que aún incluya $A_i$.

Para $i=1$, es óptimo poner $A_i=0$ porque cualquier valor mayor de $A_i$ hará que el conjunto de posibles valores siguientes en la LIS sea un subconjunto del conjunto de posibles valores siguientes en la LIS cuando $A_i=0$.

Podemos usar $2$ Árboles de Segmentos. Denotémoslos como $\texttt{before}$ y $\texttt{after}$. $\texttt{before}_i$ guardará la LIS que termina con el valor $i$ sin ninguna operación realizada. $\texttt{after}_i$ guardará la LIS que termina con el valor $i$ después de realizar una operación. También denotemos $\texttt{best}_i$ como el mejor reemplazo para $A_i$.

Podemos transicionar de la siguiente forma:

La primera y la tercera transición extienden la LIS. La segunda transición se usa para aplicar la operación. Nuestro resultado final es el valor máximo en $\texttt{after}$.

Notamos que, como $A_i \leq 10^9$, necesitaremos usar compresión de coordenadas.

Implementación

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

#include <bits/stdc++.h>
using namespace std;
 
// BeginCodeSnip{Range Maximum Segment Tree}
 
class MaxSegTree {
  private:
	int len;
	vector<int> segtree;
 
  public:
	MaxSegTree(int len) : len(len), segtree(2 * len) {}
 
	void set(int ind, int val) {
		ind += len;
		for (segtree[ind] = max(segtree[ind], val); ind > 1; ind >>= 1) {
			segtree[ind >> 1] = max(segtree[ind], segtree[ind ^ 1]);
		}
	}
 
	int range_max(int from, int to) {
		int max_ = 0;
		for (from += len, to += len; from < to; from >>= 1, to >>= 1) {
			if ((from & 1) != 0) { max_ = max(max_, segtree[from++]); }
			if ((to & 1) != 0) { max_ = max(max_, segtree[--to]); }
		}
		return max_;
	}
};
 
// EndCodeSnip
 
int main() {
	int n;
	cin >> n;
 
	vector<int> a(n);
	map<int, int> compressed;
	vector<int> best(n, 0);
 
	for (int i = 0; i < n; i++) { cin >> a[i]; }
	vector<int> val = a;
	val.push_back(0);
 
	for (int i = 0; i < n - 1; i++) { val.push_back(val[i] + 1); }
	sort(val.begin(), val.end());
	val.erase(unique(val.begin(), val.end()), val.end());
 
	for (int i = 0; i < val.size(); i++) { compressed[val[i]] = i; }
 
	for (int i = 1; i < n; i++) { best[i] = a[i - 1] + 1; }
 
	MaxSegTree before(2 * n);
	MaxSegTree after(2 * n);
 
	for (int i = 0; i < n; i++) {
		after.set(compressed[a[i]], after.range_max(0, compressed[a[i]]) + 1);
		after.set(compressed[best[i]], before.range_max(0, compressed[best[i]]) + 1);
		before.set(compressed[a[i]], before.range_max(0, compressed[a[i]]) + 1);
	}
 
	cout << after.range_max(0, 2 * n) << '\n';
	return 0;
}