[TIOJ] 1271. [IOI 2012] Scrivener 斯克里夫尼

題目連結:http://tioj.infor.org/problems/1271

---

應該很明顯可以用持久化資料結構做掉，如果知道有rope這東東的話可以直接拿來用，這題就被秒掉了。不過我們還是該秉持個手寫資料結構，所以我就寫了個持久化treap，而因為我每次插入的時候都保證key是遞增的，所以可以不用寫split把它拆掉再合起來，算是一個小常數優化(?，不過注意一下因為treap並不是保證logN的，所以有可能有幾條太長的路徑，導致MLE掉，這裡可能要多試幾次，或者直接用個7122這神秘數字避免(?

#include "lib1271.h"
#include <random>
#include <ctime>
#include <algorithm>
#define copyNode(a,b) a->l=b->l;\
						a->r=b->r;\
						a->val=b->val;\
						a->pri=b->pri;\
						a->key=b->key;
#define N 1000000
std::minstd_rand rd(7122);

struct Treap{
	int key;
	unsigned short pri;
	char val;
	Treap *l, *r;
	Treap(){}
	Treap(char c,int k){
		pri=rd();
		key=k;
		val=c;
		l=r=nullptr;
	}
};
int sizes[N+1]={0};
Treap* treaps[N+1]={nullptr};
int opt=0;
Treap __[9*N];
int _sz=0;
inline Treap* gNode(){return &__[_sz++];}
inline Treap* gNode(char c, int k){
	__[_sz].pri=rd();
	__[_sz].key=k;
	__[_sz].val=c;
	__[_sz].l=__[_sz].r=nullptr;
	return &__[_sz++];
}
Treap* Merge(Treap* a, Treap* b){
	if(!a||!b) return a?a:b;
	if(a->pri>b->pri){
		auto aa=gNode();
		copyNode(aa,a);
		if(aa->key>b->key) aa->l=Merge(aa->l, b);
		else aa->r=Merge(b, aa->r);
		return aa;
	}else{
		auto bb=gNode();
		copyNode(bb,b);
		if(bb->key>a->key) bb->l=Merge(bb->l, a);
		else bb->r=Merge(a, bb->r);
		return bb;
	}
}
char Find(Treap* tt, int k){
	if(tt->key==k)return tt->val;
	else if(tt->key>k) return Find(tt->l, k);
	else return Find(tt->r, k);
}

void Init(){
	_sz=0;
	opt=0;
	std::fill(treaps, treaps+N+1, nullptr);
	std::fill(sizes, sizes+N+1, 0);
}
void TypeLetter(char c){
	if(opt){
		treaps[opt]=treaps[opt-1];
		sizes[opt]=sizes[opt-1];
	}
	treaps[opt]=Merge(treaps[opt], gNode(c, sizes[opt]));
	sizes[opt]++;
	opt++;
}
void UndoCommands(int t){
	treaps[opt]=treaps[opt-t-1];
	sizes[opt]=sizes[opt-t-1];
	opt++;
}
char GetLetter(int k){
	return Find(treaps[opt-1], k);
}