[BOJ 17411] 가장 긴 증가하는 부분수열 6

Link

문제 링크

Problem

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열과 개수를 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이고, 1개이다. A = {10, 20, 30, 10, 20, 30}인 경우에는 가장 긴 증가하는 부분 수열의 길이는 3이고, 4개가 있다.

Input

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000)

Solution Part I

일단 LIS 문제이고, LIS 문제는 대표적으로 $\mathcal O(N^2)$과 $\mathcal O(NlgN)$으로 풀 수 있음이 알려져있다.

$\mathcal O(N^2)$ 같은 경우 $i$번째 수에 대해 $i-1$번째까지의 LIS를 이용한 dp를 사용하면 되고, $\mathcal O(NlgN)$같은 경우엔 1. Lower bound를 활용하여 길이를 구하거나 2. Segment tree를 이용하여 길이를 구하여야 한다.

하지만, 1번 방법(Lower bound)를 활용하는 방법은 길이를 구하는 것 이외의 작업은 하지 못한다. 다른 말로, 문제에서 요구하는 부분 수열의 개수를 구하는 것이 불가능하다.

따라서, 부분 수열의 개수를 구하기 위해서는 segment tree를 활용하여 구해야 한다.

일단 segment tree를 이용하여 LIS를 구하는 로직을 알아보자.

Solution Part II

수열 $\{a_1,~a_2,~\cdots,~a_n\}$에 대해 LIS를 구한다고 가정하자.

일단, 세그먼트 트리의 $i$번째 Leaf node의 정의를 $i$번째로 작은 숫자에서 끝이나는 수열 중 가장 긴 증가하는 부분 수열의 길이를 반환한다 정의하자.

예를 들어, 수열이 $10,~20,~40,~30,~50$이 있으면 $3$번째 Leaf node 같은 경우 수열에서 $3$번째로 작은 수, 즉 $30$으로 끝이 나는 LIS의 길이를 반환하는 것이다. 현 수열에서는 $10,~20,~30$을 뽑으면 되므로 $3$이다.

이렇게 되면 바로 답(실제 LIS) 같은 경우 왼쪽 child node에서의 LIS의 최장길이와 오른쪽 child node에서의 LIS의 최장길이를 비교한 이후 더 긴애를 채택하면 된다.

다만... update 과정이 다소 어려운데, 만약 $i$번째로 큰 숫자로 끝이 나야하면 그 이전에는 $i-1$번째의 숫자들밖에 오지 못한다. 따라서 $i$번째로 끝나는 수열의 LIS는 (끝나는 숫자가 첫 번째에서 $i-1$번째로 작은 수로 끝날 때의 LIS의 길이)+1이다.

node의 입장에서 보면 ($1$~$(i-1)$까지의 LIS 값) + 1 이 될 것이다.

Solution Part III

이를 이용하여 개수를 구해보자.

LIS의 update 과정에서 ($1$~$i-1$까지의 LIS)의 개수가 $K$개이면, $i$번째로 작은 숫자로 끝나는 수열의 LIS의 개수도 $k$개이다. 저 LIS들의 뒤에 숫자만 붙여주는 것이니까 말이다!

따라서, LIS 길이를 업데이트 해 줄때 개수도 동시에 업데이트를 해준다.

만약, 좌우의 LIS의 최대길이가 다르다면 더 큰쪽을 뽑으면 되지만, 만약 같을 경우 어느쪽을 뽑아도 상관이 없으므로 두개를 더해주어야 한다.

세그먼트 트리 특성 상 반으로 갈라서 탐색을 계속하기 때문에 답을 구하는 과정에서도 두 개를 더해주는 과정을 거쳐야 한다.

또한, 값의 범위가 -10억에서 10억이므로 좌표압축을 시행해주어야 한다.

업데이트 과정이 $lg N$, 값을 구하는 과정이 $lg N$이고 이를 $N$번 반복하므로 시간복잡도는 $\mathcal O(NlgN)$이다. (이론상..)

코드

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
#define x first
#define y second
#define MOD 1000000007
 
pii seg[4000007];
// seg_tree, which type of node is pair: {length, count}
// 1. If left(or right)'s length is larger than others, left(or right)'s node = self node
// 2. If length of left node and right node are same, self node's value = {length, count_left + count_right}
// When we update value at position i, perform following logic
// First, Coordinate compression of a[i] is t, find the maximum length of 1 ~ t-1
// Second, update value above logic
// TODO: Coordinate compression of input values => initation
 
pii add_pii(pii a, pii b) {
    if(a.x > b.x) return a;
    else if(a.x < b.x) return b;
    return {a.x, (a.y + b.y)%MOD};
}
 
pii update(int st, int en, int nd, int ch, pii val) {
    if(ch < st || en < ch) return seg[nd];
    if(st == en) return seg[nd] = add_pii(seg[nd], val);
    pii left = update(st, (st+en)/2, nd*2, ch, val);
    pii right = update((st+en)/2+1, en, nd*2+1, ch, val);
    return seg[nd] = add_pii(left, right);
}
 
pii ans(int st, int en, int rst, int ren, int nd) {
    if(rst > ren) return {0, 0};
    if(ren < st || en < rst) return {0, 0};
    if(rst <= st && en <= ren) return seg[nd];
    pii left = ans(st, (st + en)/2, rst, ren, nd*2);
    pii right = ans((st+en)/2+1, en, rst, ren, nd*2+1);
    return add_pii(left, right);
}
 
int main() {
    int n, c[1000007];
    vector<int> a, sa;
    scanf("%d", &n);
    for(int i=0, x;i<n;i++) scanf("%d", &x), a.push_back(x);
    sa = a;
    sort(sa.begin(), sa.end());
    sa.erase(unique(sa.begin(), sa.end()), sa.end());
    for(int i=0;i<n;i++) c[i] = lower_bound(sa.begin(), sa.end(), a[i]) - sa.begin() + 1;
    int sz = sa.size();
    // seg tree update
    for(int i=0;i<n;i++) {
        pii f = ans(1, sz, 1, c[i]-1, 1);
        update(1, sz, 1, c[i], {f.x + 1, max(f.y, 1)});
    }
    printf("%d %d\n", seg[1].x, seg[1].y);
    return 0;
}