Increasing Subsequence II

Explicación

Sea $dp[i]$ la cantidad de subsecuencias crecientes de $x$ que terminan a la derecha del índice $i$ . Notar que $dp[i]$ se puede calcular como la suma de todos los $dp[j]$ donde $j < i$ y $x_j < x_i$ .

De forma naive, esto da una solución $\mathcal O(N^2)$ . Para acelerarlo, podemos hacer compresión de coordenadas y luego suma de rango.

Más específicamente, ordenamos todos los números de $x$ y mapeamos cada número distinto a su índice en el arreglo ordenado. Esto se conoce como compresión de coordenadas, y hace que el rango de los números sea significativamente más chico.

Con esto, podemos crear un Árbol de Fenwick (BIT), donde cada valor empieza en 0. A medida que recorremos $x$ , $dp[i]$ sería la suma de los valores en las posiciones $j<k$ del BIT, donde $k$ es el índice al que se mapea $x_i$ . Luego incrementamos la posición $k$ del BIT en $dp[i]$ como preparación para el siguiente elemento de $x$ .

Implementación

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

C++Java


#include <bits/stdc++.h>
 
using namespace std;
 
const int MOD = 1e9 + 7;
const int MX = 2e5 + 5;
 
int bit[MX];
int n;
 
void upd(int i, int val) {
	for (; i <= n; i += (i & (-i))) { bit[i] = (bit[i] + val) % MOD; }
}
 
int query(int i) {
	int res = 0;
	for (; i; i -= (i & (-i))) { res = (res + bit[i]) % MOD; }
	return res;
}
 
int main() {
	cin >> n;
	map<int, int> m;
	vector<int> ar(n);
	for (int i = 0; i < n; i++) {
		cin >> ar[i];
		m[ar[i]]++;
	}
	int co = 0;
	for (auto &cur : m) { cur.second = ++co; }
	for (int &x : ar) { x = m[x]; }
	int sol = 0;
	for (int x : ar) {
		int subseq = 1 + query(x - 1);
		sol = (sol + subseq) % MOD;
		upd(x, subseq);
	}
	cout << sol << '\n';
}


import java.io.*;
import java.util.*;
public class increasingsubsequencesII {
	static final int mod = (int)(1e9 + 7);
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter pw = new PrintWriter(System.out);
		int N = Integer.parseInt(br.readLine());
		int[] nums = new int[N];
		int[] sorted = new int[N];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			sorted[i] = nums[i] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(sorted);
		Map<Integer, Integer> mp = new HashMap<>();
		for (int i = 0; i < N; i++) { mp.put(sorted[i], i); }
		BIT bit = new BIT(N);
		int ret = 0;
		for (int i : nums) {
			int curr = bit.sum(mp.get(i) - 1) + 1;
			bit.update(mp.get(i), curr);
			ret += curr;
			ret %= mod;
		}
		pw.println(ret);
		pw.close();
		br.close();
	}
	static class BIT {
		public int[] bit;
		public BIT(int N) { bit = new int[N + 1]; }
		public int sum(int r) {
			r++;
			int ret = 0;
			while (r > 0) {
				ret += bit[r];
				ret %= mod;
				r -= r & -r;
			}
			return ret;
		}
		public void update(int idx, int v) {
			idx++;
			while (idx < bit.length) {
				bit[idx] += v;
				bit[idx] %= mod;
				idx += idx & -idx;
			}
		}
	}
}