UVA 12538 Version Controlled IDE 解題報告

題意：給三種操作　

１．在ｐ位置插入一個字符串．

２．從ｐ位置開始刪除長度為ｃ的字符串

３．輸出第ｖ個歷史版本中從ｐ位置開始的長度為ｃ的字符串

解法：可以用平衡樹做，但是不會．後來又聽說可一用一個叫roap的神奇的STL，學習了一下，用法基本和string一樣．roap的內部是用平衡樹實現的，歷史版本和當前版本可以共享一些內存，插入和刪除整段字符串效率很高．是可持久化的數據結構．

//Time: 952 MS
#include <iostream>
#include <ext/rope>
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<<tmp<<"\n";
		}
	}
}