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

문제 링크 : https://www.acmicpc.net/problem/17411

문제 소개

수열이 주어졌을 때 가장 긴 증가하는 부분 수열의 길이 와 그 갯수를 출력하시오. 

문제 풀이 

가장 긴 증가하는 부분 수열 즉 LIS를 $O(NlgN)$에 구하는 방법은 여러가지가 있다. 간단한 코딩으로는 lower_bound를 사용할 수 있으며, 이분탐색도 가능하며, 세그먼트 트리도 가능하다. 이 글에서는 세그먼트 트리를 활용한 방법을 설명하고 이를 이용하여 이 문제를 해결하는 방법을 설명하려고 한다.

$O(NlgN)$ LIS by segment tree

DP로 LIS 를 찾을 때 i번째 수를 마지막으로 하는 LIS값이 Li고, 수열의 값이 Ai라면 우리는 어떤 i에 대해서 1~i-1중 Ai보다 작은 값중 가장 큰 Li를 찾아야 한다. 이는 각 i에 대해서 아래와 같은 형식으로 할 수 있다.
1. 1~Ai-1에서 구간 최댓값을 구한다. 이때 Li 값은 구한 최댓값+1이다.
2. Ai위치에 Li값을 업데이트 한다.
3. 위 과정을 1에서 부터 n까지 순서대로 반복한다.
각 i마다 2번 행동을 하는 시점에서 1~Ai-1에 업데이트 된 값들은 Ai보다 작은 값들을 가지는 위치들이며, i 이전에 있는 위치로 LIS에서 Ai가 그 뒤에 오는 조건을 만족하는 값들이다. 따라서 그 중 가장 큰 Li 값에 +1을 함으로써 수열의 i번째 수를 사용하는 가장 큰 LIS값을 구할 수 있다. 

이제 위의 방법을 이용하여 세그먼트 트리의 노드에 좀 변형을 주어서 문제를 해결해보자. 우리는 LIS와 그 갯수를 알아야 하므로, 그냥 그대로 노드에 LIS값과 그 갯수를 같이 저장해 주면 된다. 두 자식노드의 구간 최대 LIS값이 다르면 더 큰 값을 가진 노드가 그대로 부모노드가 되고, 두 자식노드의 구간 최대 LIS값이 같다면 부모노드의 구간 최대 LIS값은 그 값과 동일하며, 갯수는 두 자식노드의 각각의 갯수를 합친 값이 될 것이다. 따라서 LIS와 그 갯수를 한 번에 구할 수 있다.

코딩을 하는 과정에서 Ai의 범위상, 위치에 업데이트를 바로 할 수는 없다. 따라서 좌표 압축을 해야 문제를 해결할 수 있다. 

코드

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
 
struct poi{
    ll idx, val;
};
poi arr[1010101];
poi tree[4040404];
 
bool sf(poi a,poi b){
    if(a.val==b.val) return a.idx>b.idx;
    return a.val<b.val;
}
 
bool sf2(poi a,poi b){
    if(a.idx!=b.idx) return a.idx<b.idx;
    return a.val<b.val;
}
 
 
poi mergee(poi a,poi b){
    poi ret;
    if(a.val>b.val) ret=a;
    else if(a.val<b.val) ret=b;
    else{
        ret.val=a.val;
        ret.idx=a.idx+b.idx;
    }
    return ret;
}
 
poi upt(ll idx,poi k,ll s,ll e,ll nod){
    if(idx<s||idx>e) return tree[nod];
    if(s==e) return tree[nod]=k;
    poi a=upt(idx,k,s,(s+e)/2,nod*2);
    poi b=upt(idx,k,(s+e)/2+1,e,nod*2+1);
    if(a.val>b.val) tree[nod]=a;
    else if(a.val<b.val) tree[nod]=b;
    else{
        tree[nod].val=a.val;
        tree[nod].idx=a.idx+b.idx;
    }
    return tree[nod];
}
 
poi sol(ll l,ll r,ll s,ll e,ll nod){
    poi x;
    if(r<s||e<l) return x;
    if(l<=s&&e<=r) return tree[nod];
    poi a=sol(l,r,s,(s+e)/2,nod*2);
    poi b=sol(l,r,(s+e)/2+1,e,nod*2+1);
    if(a.val>b.val) x=a;
    else if(a.val<b.val) x=b;
    else{
        x.val=a.val;
        x.idx=a.idx+b.idx;
    }
    return x;
}
 
int main(){
    ll i,j,k,l,m,n;
    scanf("%lld",&n);
    for(i=1;i<=n;i++){
        scanf("%lld",&arr[i].val);
        arr[i].idx=i;
    }
 
    sort(arr+1,arr+1+n,sf);
    for(i=1;i<=n;i++)
        arr[i].val=i;
    sort(arr+1,arr+1+n,sf2);
 
    poi ans={0,0};
    poi x={1,0};
    upt(0,x,0,n,1);
    for(i=1;i<=n;i++){
        poi x=sol(0,arr[i].val,0,n,1);
        x.val++;
        x.idx%=1000000007;
        ans=mergee(ans,x);
        ans.idx%=1000000007;
        upt(arr[i].val,x,0,n,1);
    }
    printf("%lld %lld\n",ans.val,ans.idx);
}