UVA 12538 Version Controlled IDE 문제 풀이 보고서

제목: 세 가지 조작 을 드 립 니 다.
1. p 위치 에 문자열 을 삽입 합 니 다.
2. p 위치 부터 길이 가 c 인 문자열 삭제
3. v 번 째 역사 버 전에 서 p 위치 에서 시작 하 는 길이 가 c 인 문자열 을 출력 합 니 다.
해법: 밸 런 스 트 리 로 만 들 수 있 지만 할 수 없습니다. 나중에 rope 라 는 신기 한 STL 로 배 웠 다 고 들 었 습 니 다. 용법 은 기본적으로 string 과 같 습 니 다. roap 의 내 부 는 밸 런 스 트 리 로 이 루어 졌 습 니 다. 역사 버 전과 현재 버 전 은 메모 리 를 공유 할 수 있 고 전체 문자열 을 삽입 하고 삭제 하 는 효율 이 높 습 니 다. 지속 가능 한 데이터 구조 입 니 다.

//Time: 952 MS
#include 
#include 
using namespace std;
using namespace __gnu_cxx;
crope ro,l[50005],tmp;
char str[205];
int main()
{
	//freopen("/home/qitaishui/code/in.txt","r",stdin);
	int n,op,p,c,d,cnt,v;
	scanf("%d",&n);
	d = 0;
	cnt = 1;
	while(n--)
	{
		scanf("%d",&op);
		if(op==1)
		{
			scanf("%d%s",&p,str);
			p-=d;
			ro.insert(p,str);
			l[cnt++]= ro;
		}
		else if(op == 2)
		{
			scanf("%d%d",&p,&c);
			p-=d,c-=d;
			ro.erase(p-1,c);
			l[cnt++] = ro;
		}
		else
		{
			scanf("%d%d%d",&v,&p,&c);
			p-=d,v-=d,c-=d;
			tmp = l[v].substr(p-1, c);
			d+=count(tmp.begin(),tmp.end(),'c');
			cout<