CSES - Increasing Subsequence II

Time Complexity: $\mathcal{O}(N\log N)$

Let $dp[i]$ be the number of increasing subsequences of $x$ ending on the right of index $i$. Notice that $dp[i]$ can be calculated as the summation of all $dp[j]$ where $j < i$ and $x_j < x_i$.

Naively, this gives an $\mathcal O(N^2)$ solution. In order to speed this up, we can coordinate compress, then range sum.

More specifically, we sort all numbers in $x$ and map each distinct number to its index in the sorted array. This is known as coordinate compression, and it makes the range of the numbers significantly smaller.

With this, we can create a BIT, where each value is initially 0. As we iterate through $x$, $dp[i]$ would be the sum of the values at positions $j<k$ in the BIT, where $k$ is the index that $x_i$ maps to. We then increase position $k$ in the BIT by $dp[i]$ as preparation for the next element of $x$.

Copy
#include <bits/stdc++.h>

using namespace std;

const int MOD = 1e9 + 7;
const int MX = 2e5 + 5;

int bit[MX];
int n;

Copy
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];