모든 구간 LIS

$f(l,r)$를 구간 $[l,r]$의 LIS 길이라고 하자.

먼저 다음 값을 정의한다.

$$d_l=f(l,r)-f(l,r-1) \qquad (1 \leq l < r)$$

원소 하나를 뒤에 추가했으므로 $d_l$은 항상 $0$ 또는 $1$이다.

LIS 구간 행렬은 다음 unit-Monge 부등식을 만족한다.

$$f(l,r)+f(l+1,r-1) \leq f(l,r-1)+f(l+1,r)$$

이 부등식은 순열의 원소를 좌표평면의 점 $(i,P_i)$로 놓고 LIS를 오른쪽 위로 진행하는 최장 경로로 보면, 두 최적 경로의 교차 부분에서 꼬리를 교환하는 표준 uncrossing으로 얻을 수 있다.

부등식을 정리하면 다음을 얻는다.

$$f(l,r)-f(l,r-1) \leq f(l+1,r)-f(l+1,r-1)$$

따라서 고정된 $r$에 대하여 $d_1,d_2,\cdots,d_{r-1}$은 단조 증가한다. 각 값은 $0$ 또는 $1$이므로 어떤 경계 $t$가 존재하여 $l<t$에서는 $d_l=0$이고, $t \leq l<r$에서는 $d_l=1$이다. 경계가 $r$이면 모든 $d_l$이 $0$인 경우이다.

$r-1$까지 끝나는 모든 구간의 답을 이미 알고 있다고 하자. 중간점 $m$에 대해 한 번 질의하여 $f(m,r)$를 얻으면, 이미 알고 있는 $f(m,r-1)$과 비교하여 $d_m$이 $0$인지 $1$인지 알 수 있다. 그러므로 이분 탐색으로 경계 $t$를 찾을 수 있다.

경계 $t$를 찾은 뒤에는 다음과 같이 계산한다.

• $l<t$이면 $f(l,r)=f(l,r-1)$.
• $t \leq l<r$이면 $f(l,r)=f(l,r-1)+1$.
• $f(r,r)=1$.

오른쪽 끝점 $r$에 필요한 질의 수는 최대 $\lceil\log_2 r\rceil$번이다. $N=100$일 때 전체 질의 수는 다음과 같다.

$$\sum_{r=2}^{100}\lceil\log_2 r\rceil =1+4+12+32+80+192+252 =573$$

따라서 $600$번의 제한을 만족한다.

시간 복잡도는 답을 출력하기 위한 $O(N^2)$이고, 질의 횟수는 $O(N\log N)$이다.

Solution written by GPT5.6