문제 59
활성 구간
길이가 $N$인 정수 수열 $A_1, A_2, \cdots, A_N$이 주어진다.
$Q$개의 쿼리가 주어진다.
각 쿼리마다 $A_i \le x$인 위치들만 남겼을 때 가장 긴 연속 구간의 길이를 출력하라.
입력
첫 번째 줄에 두 정수 $N$, $Q$가 공백으로 구분되어 주어진다. $(1 \le N, Q \le 200\,000)$
두 번째 줄에 $N$개의 정수 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다. $(-10^9 \le A_i \le 10^9)$
세 번째 줄부터 $Q$개의 줄에 걸쳐 정수 $x$가 하나씩 주어진다. $(-10^9 \le x \le 10^9)$
출력
각 쿼리마다 가장 긴 연속 구간의 길이를 한 줄에 하나씩 출력한다.
예제 입력 1
7 5 5 1 4 2 3 8 6 2 3 4 5 10
예제 출력 1
1 2 4 5 7
공식 해설
질의값 $x$가 커지면 활성 위치는 추가되기만 한다. 질의를 $x$순으로 정렬하여 처리하면 비활성으로 되돌리는 연산이 필요 없다.
수열의 위치들도 $A_i$가 작은 순서로 정렬한다. 각 질의 전에 $A_i\le x$인 아직 비활성 위치를 모두 활성화한다. 새 위치의 양옆이 활성 상태라면 DSU로 합친다. 이때 원소를 당기지 않고 원래 인덱스에서 바로 이웃한 위치들만 연결한다.
각 연결 요소가 정확히 하나의 연속 활성 구간이므로 요소의 크기가 구간 길이이다. 활성화와 합치기마다 최댓값을 갱신하면 해당 질의의 답을 얻는다. 활성 위치가 없으면 $0$이다. 같은 값의 위치도 질의 전에 모두 처리해야 한다.
DSU에는 경로 압축과 크기 기준 합치기를 적용한다. 답은 원래 질의 번호에 저장하여 입력 순서대로 출력한다.
시간복잡도는 $O(N\log(N+1)+Q\log(Q+1)+(N+Q)\alpha(N))$, 공간복잡도는 $O(N+Q)$이다.
구현 · 언어별 풀이
C++ 구현
수열은 (값, 원래 인덱스), 질의는 (x, 입력 순서)의 쌍으로 저장해 각각 정렬한다. 활성 여부는 vector<char>, 연결 요소는 DSU로 관리한다. 답은 원래 질의 순서에 저장하고, 이웃을 합치기 전에 인덱스 범위를 확인한다.
C 구현
(값,원래 위치)와 (질의값,질의 번호)를 구조체 배열로 정렬한다. 활성화 시 원래 좌우 이웃과 DSU를 합친다. 질의 답은 원래 질의 번호에 저장하며 같은 값의 원소를 모두 활성화한 뒤 답한다.
Python 구현
sorted(enumerate(A), key=lambda t: t[1])와 정렬한 질의를 사용한다. 압축된 값의 인접 위치가 아니라 원래 배열의 이웃과 union한다. 답 리스트에는 질의 원래 인덱스로 저장한다.
Java 구현
값·인덱스를 함께 정렬하고 int[] DSU와 boolean[] active를 사용한다. A[i] <= x인 원소를 전부 활성화한 뒤 최대 크기를 답한다. 같은 임계값에서 중간 상태를 출력하지 않는다.
Rust 구현
(값,원래 인덱스) 튜플과 질의 튜플을 정렬한다. Vec<bool> active와 DSU를 사용하며 i>0, i+1<N 확인 후 이웃을 합친다. 정렬 뒤에도 원래 인접 관계를 유지한다.
JavaScript 구현
원소는 값과 원래 위치, 질의는 기준값과 원래 번호를 함께 보관해 숫자 비교 함수로 정렬한다. 활성화는 원래 배열의 좌우 이웃으로 해야 하므로 정렬한 순번을 DSU 정점 번호로 사용하지 않는다.
현재 질의 $x$ 이하인 원소를 모두 활성화한 뒤 가장 큰 연결 요소의 크기를 기록한다. 값이 같은 여러 위치도 이번 답을 기록하기 전에 처리해야 한다. 새 위치를 켜면 크기를 $1$로 초기화하고, 활성화된 이웃과 서로 다른 집합을 합칠 때 두 크기를 더한다. 활성화와 합치기마다 전체 최댓값을 갱신하며, 활성 위치가 없으면 답은 $0$이다. 연결 요소의 개수는 구간 길이가 아니므로 답으로 사용하지 않는다.
Uint8Array로 활성 여부를, Int32Array로 부모·크기를 저장한다. find는 반복문과 경로 압축으로 작성하고 크기 기준으로 합친다. 답은 질의 원래 번호에 넣은 뒤 입력 순서로 출력한다.