Overlapping Intervals

인덱스는 설명에서 $0$부터 시작한다고 하자.

$K\ge 2$인 답에서, 어느 순간 연속한 두 구간의 왼쪽 끝이 $a<b$라고 하자. 먼저 $a$에서 시작한 구간을 닫고, 그 뒤에 새로운 구간의 왼쪽 끝을 골라야 한다.

$\operatorname{dp}[a][b]$를 왼쪽 끝이 $a,b$인 두 구간에서 시작하여 만들 수 있는 구간 개수의 최댓값이라고 정의한다. 불가능하면 $0$이다.

$b$보다 뒤에서 $S_a$와 같은 문자가 처음 나타나는 위치를 $c$라고 하자. 그런 위치가 없다면 $\operatorname{dp}[a][b]=0$이다. 에서 시작한 구간의 오른쪽 끝을 보다 더 뒤의 같은 문자로 잡는 것은 이후에 사용할 수 있는 위치를 줄이기만 하므로, 항상 가장 이른 위치 만 고려하면 충분하다.

두 구간만으로 끝내려면 $c$보다 뒤에 $S_b$와 같은 문자가 존재해야 한다. 이 경우 $\operatorname{dp}[a][b]\ge 2$이다.

세 구간 이상을 만들려면 $c$보다 뒤의 어떤 위치 $d$를 새로운 구간의 왼쪽 끝으로 고른다. 이후의 문제는 왼쪽 끝이 $b,d$인 상태와 같으므로 다음 점화식을 얻는다.

$$\operatorname{dp}[a][b]=\max\left(2,\ 1+\max_{d>c}\operatorname{dp}[b][d]\right)$$

여기서 첫 번째 항은 실제로 $c$보다 뒤에 $S_b$가 존재할 때만 사용할 수 있고, 두 번째 항은 해당 범위에 양수인 상태가 있을 때만 사용할 수 있다.

각 $b$에 대해 다음 suffix maximum을 관리한다.

$$\operatorname{suf}[b][x]=\max_{d\ge x}\operatorname{dp}[b][d]$$

그러면 점화식의 최댓값을 $O(1)$에 구할 수 있다. $\operatorname{dp}[a][b]$는 $\operatorname{dp}[b][d]$만 참조하고 항상 $a<b<d$이므로, 를 큰 값부터 작은 값 순서로 처리하면 된다.

마지막으로 모든 $\operatorname{dp}[a][b]$의 최댓값을 구한다. 같은 문자가 두 번 이상 등장하지만 두 구간을 만들 수 없는 경우에는 답이 $1$이며, 같은 문자가 한 번도 반복되지 않으면 답은 $0$이다.

다음 등장 위치는 각 위치와 문자에 대해 전처리할 수 있다. 상태 수와 suffix maximum의 크기가 모두 $O(N^2)$이므로 시간 복잡도는 $O(N^2)$, 메모리 복잡도는 $O(N^2)$이다.

Solution written by GPT5.6