Fat Sequence

$A_i$에서 끝나는 가장 긴 증가하는 부분수열의 길이를 $A_i$의 레벨 $L_i$라 하고, $K = \max L_i$라 하자. 모든 $L_i$는 잘 알려진 lower\_bound 방식의 LIS 알고리즘으로 $O(N \log N)$에 구할 수 있다.

관찰 1. 길이 $K$인 증가하는 부분수열의 $k$번째 원소는 레벨이 정확히 $k$이다. 앞의 $k$개 원소가 증가하는 부분수열을 이루므로 레벨은 $k$ 이상이다. 레벨이 $k$보다 크다면 그 뒤의 $$개 원소를 이어 붙여 길이가 보다 긴 증가하는 부분수열을 만들 수 있으므로 모순이다.

관찰 2. 레벨이 같은 원소들을 인덱스 순으로 나열하면 값이 감소하지 않는다. $j < i$, $L_j = L_i$인데 $$라면 를 뒤에 붙일 수 있으므로 이 되어 모순이다.

관찰 3. 위 레벨부터 가장 큰 값을 고르면 된다. 다음과 같이 $g_K, g_{K-1}, \cdots, g_1$을 정한다.

• $g_K$는 레벨 $K$인 원소 중 가장 앞에 있는 것, 즉 값이 가장 큰 것이다.
• $g_k$ ($k<K$)는 레벨 인 원소 중 값이 보다 작은 것들 가운데 가장 앞에 있는 것이다. 관찰 2에 의해 이것은 그중 값이 가장 큰 원소이다.

$g_{k+1}$의 레벨이 $k+1$이므로, $g_{k+1}$보다 앞에 있으면서 값이 더 작은 레벨 원소가 존재한다. 는 그런 원소들 중 가장 앞에 있으므로 인덱스도 자동으로 보다 앞이다. 따라서 는 길이 인 증가하는 부분수열이다.

이제 임의의 길이 $K$인 증가하는 부분수열 $h_1, h_2, \cdots, h_K$를 생각하자. 관찰 1에 의해 의 레벨은 이다. 부터 내려가며 임을 보인다. 는 의 정의에서 바로 나온다. 이라면 이고, 는 레벨 이면서 보다 작은 값 중 최댓값이므로 이다.

따라서 모든 $k$에 대해 $h_k \leq g_k$이고, $g$가 뚱뚱한 수열이다. 합이 같다면 모든 원소가 같아야 하므로 뚱뚱한 수열의 원소 값은 항상 유일하다.

구현. 원소들을 레벨별로 인덱스 순서를 유지하며 모은다. 각 레벨의 목록을 앞에서부터 훑으며 값이 $g_{k+1}$보다 작은 첫 원소를 찾으면 되고, 각 목록을 한 번씩만 훑으므로 이 부분은 $O(N)$이다.

int bound = INT_MAX;
for (int k = K - 1; k >= 0; k--) {
    int p = st[k];
    while (a[ord[p]] >= bound) p++;
    pick[k] = a[ord[p]];
    bound = pick[k];
}

전체 시간복잡도는 $O(N \log N)$이다. 합은 최대 약 $10^{15}$이므로 64비트 정수를 써야 한다.

뒤에서부터 훑으며 처음 만나는 원소를 고르는 일반적인 LIS 역추적은 각 레벨에서 가능한 가장 작은 값을 고르므로 틀린다. 증가가 강증가라는 점에도 주의해야 한다. lower\_bound 대신 upper\_bound를 쓰면 같은 값이 있는 입력에서 틀린다.

서브태스크별 풀이.

• 서브태스크 1: 모든 부분수열을 확인한다. $O(2^N N)$.
• 서브태스크 2: $(\text{길이}, \text{합})$의 사전순 최댓값을 상태로 두는 $O(N^2)$ DP와 역추적.

Solution written by ClaudeOpus5.5