구사과

티스토리 렌더링 문제로 수식이 많이 깨진다. 일단 깨진 형태로 올려두지만 쉽게 볼 수 있는 PDF를 첨부한다. PDF를 보는 것을 추천한다. 이번 글에서는 다음과 같은 쿼리를 수행하는 자료 구조에 대해 다룬다: 길이 $N$ 의 수열 $A$ 와 $Q$ 개의 쿼리 $1 \le i \le j \le N$ 가 주어질 때, $A[i], A[i + 1], \ldots, A[j]$ 의 최장 증가 부분 수열 (Longest Increasing Subsequence, LIS) 를 계산하라. LIS 문제의 경우 동적 계획법으로 해결할 수 있는 가장 기초적인 문제 중 하나로, 수학적으로 여러 의미를 가지기 때문에 변형된 문제들이 다방면으로 연구되고 있다. 위와 같은 쿼리 문제는 다들 자료 구조 문제를 고민해 보다가 한번쯤 ..

문자열의 부분문자열에 대한 복잡한 문제를 풀 때 Suffix Array와 같은 접미사 구조 는 아주 강력한 도구가 된다. SCPC 2021 3번, 서울 리저널 2022 H 등 여러 중요한 대회에서도 이러한 접미사 구조를 응용한 문제들이 정말 많이 나온다. 한국에서 많은 사람들이 알고 있는 접미사 구조로는 Suffix Array 가 있다. Suffix Array는 모든 문자열의 접미사를 정렬한 순열로, 흔히 부분문자열 탐색 쿼리를 빠르게 처리하거나 두 접미사의 LCP를 구할 때 많이 쓰인다. 문자열 접미사 구조 중 알려진 자료구조는 크게 Suffix Array, Suffix Tree, Suffix Automaton 이 있는데, 한국에서는 Suffix Array만이 알려져 있는 편이고, 그 외 다른 자료구조..

Codeforces에 올린 글을 보관 목적으로 블로그에도 올립니다. Yesterday I participated in a local contest involving a problem about Monge arrays. I could've wrote some d&c optimization, but I got bored of typing it so I copypasted maroonrk's SMAWK implementation to solve it. Today, I somehow got curious about the actual algorithm, so here it goes. 1. Definition I assume that the reader is aware of the concept o..