BOJ 13555 증가하는 부분 수열

증가하는 부분 수열
(http://boj.kr/13555)

앞의 원소부터 차례대로 원소의 값을 인덱스로 해서 배열에 저장해두면,
현재 원소의 값보다 작은 인덱스에 저장된 것들은 현재 원소보다 앞에 있고 작은 것들이라는 의미이다.
이 방법으로 개수도 구할 수 있다.

\(D_{i j}\)를 \(i\)번째 항으로 끝나는 길이가 \(j\)인 증가하는 부분 수열의 개수라고 할 때,
앞의 방법대로 구할 수 있다.

인덱스가 작은 항부터 넣을 때, 길이가 \(j\)인 수열을 만들려면 자신의 값보다 앞에 있는 것들 중 길이가 \(j-1\)인 것들에 현재 원소를 붙여야 한다.
즉, 자신의 값보다 앞에 있는 것들의 길이가 \(j-1\)인 수열 개수의 합이다.
\(D_{i j}=D_{k j-1}(k=1, 2, 3, \cdots, i-1 \text{이고 } \text{arr}[k]<\text{arr}[i])\)

이 합을 구할 때 \(O(N)\)으로 하면 시간초과가 나기 때문에 \(O(\log\,N)\)으로 구할 수 있는 세그먼트 트리나 펜윅 트리 등을 사용해야 한다.

세그먼트 트리로 구현했을 때 시간초과가 나길래 펜윅 트리로 했다.

#include <bits/stdc++.h>
 
const int r = 5000000;
 
int arr[100001], tree[51][100001], d[51][100001];
 
void update(int y, int x, int val) {
    while (x <= 100000) {
        tree[y][x] = (tree[y][x] + val) % r;
        x += x & -x;
    }
}
 
int sum(int y, int x) {
    int sum = 0;
 
    if (y == 0)
        return 1;
 
    while (x > 0) {
        sum = (sum + tree[y][x]) % r;
        x -= x & -x;
    }
 
    return sum;
}
 
int main() {
    int n, k;
 
    scanf("%d %d", &n, &k);
 
    for (int i = 1;i <= n;++i)
        scanf("%d", &arr[i]);
 
    for (int i = 1;i <= n;++i) 
        for (int j = 1;j <= k;++j) {
            d[j][i] = sum(j - 1, arr[i] - 1);
            update(j, arr[i], d[j][i]);
        }
 
    int sum = 0;
    for (int i = 1;i <= n;++i)
        sum = (sum + d[k][i]) % r;
 
    printf("%d", sum);
 
    return 0;
}