문제 60
문자열 편집기
문자열 $S$가 있다. 문자의 위치는 $1$부터 $\lvert S \rvert$까지이다. $Q$개의 쿼리를 순서대로 처리하라.
쿼리는 다음 중 하나이다.
1 p T: 문자열 $T$를 $S$의 $p$번째 문자 앞에 삽입한다. $p=\lvert S \rvert+1$이면 맨 뒤에 삽입한다.2 l r: $S$의 $l$번째 문자부터 $r$번째 문자까지 삭제한다.3 l r: $S$의 $l$번째 문자부터 $r$번째 문자까지 출력한다.4 l r: $S$의 $l$번째 문자부터 $r$번째 문자까지 잘라낸 뒤 맨 앞으로 이동한다.5 l r: $S$의 $l$번째 문자부터 $r$번째 문자까지 잘라낸 뒤 맨 뒤로 이동한다.
입력
첫 번째 줄에 문자열 $S$가 주어진다. $(1 \le \lvert S \rvert \le 100\,000)$
두 번째 줄에 정수 $Q$가 주어진다. $(1 \le Q \le 200\,000)$
세 번째 줄부터 $Q$개의 줄에 걸쳐 쿼리가 하나씩 주어진다.
모든 쿼리는 실행 직전 문자열의 길이를 기준으로 올바르게 주어진다.
모든 문자열은 알파벳 소문자로 이루어져 있다. 삽입되는 문자열의 길이의 합과 출력되는 문자열의 길이의 합은 각각 $200\,000$ 이하이다.
출력
3 l r 쿼리마다 해당 부분 문자열을 한 줄에 하나씩 출력한다.
예제 입력 1
abcdef 8 3 1 6 4 2 4 3 1 6 5 1 2 3 1 6 1 4 xyz 2 2 5 3 1 5
예제 출력 1
abcdef bcdaef daefbc dzfbc
공식 해설
문자열을 옮기지 말고 트리를 나누기
연속 배열에서 긴 구간을 옮기면 많은 문자를 복사해야 한다. 대신 중위 순회 순서가 문자열이 되도록 암시적 Treap을 만든다. 각 노드는 문자 하나, 무작위 우선순위, 두 자식과 서브트리 크기를 저장한다.
왼쪽 서브트리의 크기로 각 문자의 현재 위치를 알 수 있으므로 별도의 위치 키는 필요 없다. 핵심 연산은 처음 $k$글자와 나머지로 나누는 분할, 그리고 앞 문자열과 뒤 문자열을 잇는 병합이다. 분할할 때는 서브트리 크기로 내려갈 방향을 고르고, 병합할 때는 우선순위가 높은 루트를 고른다. 바뀐 노드의 크기를 다시 계산한다.
모든 명령을 분할과 병합으로 표현하기
구간 $[l,r]$을 다룰 때 처음 $l-1$글자를 분리하고, 나머지에서 $r-l+1$글자를 다시 분리한다. 그러면 문자열이 앞부분 $A$, 대상 구간 $B$, 뒷부분 $C$로 나뉜다.
삭제 결과는 $A+C$, 맨 앞으로 이동한 결과는 $B+A+C$, 맨 뒤로 이동한 결과는 $A+C+B$이다. 출력은 $B$를 중위 순회한 뒤 $A+B+C$로 다시 합친다. 삽입은 처음 $p-1$글자와 나머지 사이에 새 문자열의 트리를 넣으면 된다.
분할과 병합은 문자들의 상대 순서를 보존하므로 이 표현 그대로 문제의 명령이 된다. 빈 구간은 빈 트리로 다루면 맨 앞·맨 뒤 삽입이나 전체 삭제도 같은 방식으로 처리된다.
복잡도
무작위 우선순위를 독립적으로 정하면 기대 트리 높이는 로그이다. 초기 길이를 $n_0$, 삽입·출력 문자의 총수를 $I,R$, 최대 문자열 길이를 $L$이라 하자. 새 문자열도 문자를 하나씩 병합해 만들면 기대 시간복잡도는 $O((n_0+I+Q)\log(L+1)+R)$이다. 모든 생성 노드를 보관하는 구현도 공간복잡도는 $O(n_0+I)$이다.
구현 · 언어별 풀이
C++ 구현
노드 구조체에 문자, 두 자식의 인덱스, 우선순위와 크기를 저장하고 split, merge 함수를 작성한다. 우선순위는 mt19937_64로 생성한다. 노드 배열이 재할당될 수 있다면 노드의 참조를 새 노드 생성 뒤까지 보관하지 말고 인덱스를 사용한다. 단순한 string::insert나 erase를 반복하면 긴 구간 이동의 비용을 줄일 수 없다.
C 구현
implicit treap의 노드 풀에 문자·priority·size·left/right 인덱스를 둔다. split/merge로 부분 문자열을 옮기며 직접 복사하지 않는다. 풀을 realloc해도 노드 간 참조가 깨지지 않도록 포인터 대신 인덱스를 저장한다.
Python 구현
문자열 슬라이스를 매 질의마다 이어 붙이면 선형 시간이 든다. implicit treap의 노드 인덱스를 left/right/size 배열과 문자 배열에 저장하고 무작위 priority를 둔다. split/merge 뒤 size를 갱신하고 출력할 구간만 순회한다.
Java 구현
StringBuilder의 중간 삽입·삭제는 이 제한에서 선형이므로 implicit treap을 사용한다. primitive 노드 풀 배열과 SplittableRandom priority를 두고 split/merge로 위치를 처리한다. 불필요한 문자열 전체 복사를 피한다.
Rust 구현
Vec<Node>에 알고리즘에 필요한 문자·priority·size·자식 인덱스만 둔다. split/merge에서는 필드를 복사한 뒤 재귀 호출하고 다시 저장해 borrow를 분리한다. 무작위 priority로 기대 로그 높이를 유지한다.
JavaScript 구현
문자열의 중간 삽입·삭제마다 긴 JS 문자열을 새로 만들면 이동 비용이 누적된다. 공통 풀이의 implicit treap을 문자 노드로 구현하고, 인덱스 $0$을 빈 자식으로 두면 부분 문자열을 분리하고 다시 합칠 수 있다.
자식 번호와 서브트리 크기는 Int32Array, 문자는 Uint8Array에 저장할 수 있다. 전체 생성 노드는 초기 길이와 삽입 길이의 합인 $300\,000$ 이하이다. 각 노드에 한 번 생성한 Math.random() 우선순위를 두고 merge에서 같은 우선순위 기준을 계속 사용한다.
split(root, k)는 앞의 정확히 $k$글자와 나머지로 나눈다. 내려가거나 다시 합친 뒤 자식 크기로 현재 크기를 갱신한다. split/merge의 재귀는 임의 우선순위에 따른 기대 로그 깊이이며, 균형이 최악에도 보장되는 트리라고 설명하지 않는다.
출력 쿼리에서도 필요한 구간을 분리해 중위 순회한 뒤 원래 트리로 합쳐 돌려놓는다. 출력 순회는 스택을 사용하고, 반환되는 문자 수의 합이 $200\,000$ 이하라는 제한에 맞게 결과를 묶는다. 삭제한 구간의 노드를 다시 탐색하거나 문자열 전체를 재구성하지 않는다.