백준 24505 - blobhyperthink (C++)

문제

• 문제 링크

  
   BOJ 24505 - blobhyperthink 
  

• 문제 요약

길이 $N$의 수열이 주어진다.
이 수열에서, 길이가 $11$인 증가수열의 개수를 $10^9+7$로 나눈 나머지를 구해보자.

• 제한

TL : $2$ sec, ML : $1024$ MB




$1 ≤ N ≤ 10^5$

$1 ≤ A_i ≤ N$

알고리즘 분류

• 다이나믹 프로그래밍(dp)
• 자료 구조(data_structures)
• 세그먼트 트리(segtree)

풀이

$N$이 적당히 작았다면, 각 $i$마다 이전 수열을 순회하며 답을 계산하는 $O(N^2)$에 풀 수 있을 테지만 $N ≤ 10^5$이다.


$[A_1, A_i]$에서 길이가 $k$인 증가 수열의 개수를 구한다고 해보자.

이는 $A_1$, $A_2$, ... , $A_{i-1}$인 $A_j$에 대해, $A_i > A_j$를 만족하는 모든 $[A_1, A_j]$에서 길이가 $k - 1$인 증가 수열의 개수합과 같다.

---

$11$개의 합 세그먼트 트리를 두자.

$seg(u, x)$ : 길이가 $u$고, $x$로 끝나는 증가 수열의 개수.

각 $i$마다 $A_i$를 끝으로 하는 길이 $1, 2, ... , 11$인 증가 수열의 개수를 누적하자.

앞서 말했다시피, 길이가 $k$인 증가 수열의 개수를 계산할 땐 $k - 1$번 세그먼트 트리에 $[1, A_i-1]$만큼 합쿼리를 날리는 것과 같다.

모든 $i$에 대한 업데이트가 끝난다면, 답은 $11$번 세그먼트 트리에 $[1, 10^5]$만큼 합쿼리를 날리는 것과 같다.

시간 복잡도는 상수가 조금 붙은 $O(NlogN)$.

전체 코드

#include<bits/stdc++.h>
#define N 100001
using namespace std;
 
const int mod(1e9 + 7);
 
int seg[12][N];
void update(int u, int x, int val)
{
    for (; x < N; x += x & -x)
        if (seg[u][x] += val; seg[u][x] >= mod)
            seg[u][x] -= mod;
}
int query(int u, int x, int res = 0)
{
    for (; x; x -= x & -x)
        if (res += seg[u][x]; res >= mod)
            res -= mod;
    return res;
}
int main()
{
    int n; cin >> n;
    for (int i(1); i <= n; i++)
    {
        int x; scanf("%d", &x);
        update(1, x, 1);
        for (int k(2); k < 12; k++)
        {
            int val(query(k - 1, x - 1));
            update(k, x, val);
        }
    }
    cout << query(11, 1e5);
}

comment

끝