BOJ 9548 무제

문제 링크입니다.

문제 요약

가져다 씁시다

gcc 확장 라이브러리 중에 <ext/rope>라는 녀석이 있습니다. 문자열을 트리에 집어넣고 관리하는 컨셉인데… 자세한 내부 구현은 지적 호기심이 충만해지면 알아보고 일단은 그냥 써먹읍시다.

문자열에 문자를 삽입하고, 부분 문자열을 출력하는 쿼리를 처리해야 합니다. rope의 substr을 이용하면 문자열을 자르고, 중간에 글자를 끼워넣어 합치는 각각의 과정을 $\mathcal{O}(\log N)$에 처리할 수 있습니다.

C++을 쓰지 않으신다면… 음… 스플레이 트리와 같은 BBST를 직접 구현해서 해결할 수 있을 겁니다.

화이팅!

코드

#include<bits/stdc++.h>
#include<ext/rope>
using namespace std;
using namespace __gnu_cxx;

int main(){
	cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);
	int T; cin >> T;
	while(T--){
		rope<char> r;
		string s; cin >> s;
		r.append(s.c_str());
		while(1){
			string qry; cin >> qry;
			if(qry == "END") break;
			if(qry == "I"){
				string str; int x; cin >> str >> x;
				r = r.substr(0, x) + str.c_str() + r.substr(x, r.size()-x);
			}
			if(qry == "P"){
				int x, y; cin >> x >> y;
				cout << r.substr(x, y-x+1) << '\n';
			}
		}
	}
}