记录编号	142330	评测结果	AAAAAAAAAA
题目名称	[JSOI 2008]火星人prefix	最终得分	100
用户昵称	Asm.Def	是否通过	通过
代码语言	C++	运行时间	2.560 s
提交时间	2014-12-07 18:43:00	内存使用	3.46 MiB

#include <cctype>
#include <cstdio>
#include <iostream>
#include <ctime>
#include <cstdlib>
using namespace std;
template<typename T>inline void getd(T &x){
	char c = getchar();
	bool minus = 0;
	while(!isdigit(c) && c != '-')c = getchar();
	if(c == '-')minus = 1, c = getchar();
	x = c - '0';
	while(isdigit(c = getchar()))x = x * 10 - '0' + c;
	if(minus)x = -x;
}
/*========================================================*/
typedef unsigned long long ull;
const int maxn = 100005;
const ull p3 = 3127, p1 = 49999, p2 = 2147483647;
char tmp[maxn];
ull pow1[maxn];
int M;
struct Splay{
	int size, val;
	ull h1;
	Splay* init(int);
	Splay *son[2];
	int cmp(int k){
		if(k <= son[0]->size)return 0;
		if(k - son[0]->size == 1)return -1;
		return 1;
	}
	void update(){
		size = son[0]->size + son[1]->size + 1;
		h1 = son[0]->h1 + pow1[son[0]->size]*(p1 * son[1]->h1 + val);
	}
}Nil, *Root, Pool[maxn];
int iter = 0;
Splay* Splay::init(int v){
	val = h1 = v;
	size = 1;
	son[0] = son[1] = &Nil;
	return this;
}
inline void rot(Splay* &o, bool lr){
	Splay *t = o->son[lr];o->son[lr] = t->son[lr^1];t->son[lr^1] = o;o->update();o = t;o->update();
}
inline void find(Splay* &o, int k){
	int c = o->cmp(k);
	if(c == -1)return;
	if(c)k -= o->son[0]->size + 1;
	int c2 = o->son[c]->cmp(k), k2 = k;
	if(~c2){
		if(c2)k2 -= o->son[c]->son[0]->size + 1;
		find(o->son[c]->son[c2], k2);
		if(c == c2)rot(o, c);
		else rot(o->son[c], c2);
	}
	rot(o, c);
}
inline Splay *newT(char *str, int len){
	if(len == 1){return Pool[iter++].init(*str - 'a');}
	int mid = len >> 1;
	Splay *t = Pool[iter++].init(str[mid] - 'a');
	t->son[0] = newT(str, mid);
	if(len - mid > 1)t->son[1] = newT(str + mid + 1, len - mid - 1);
	t->update();
	return t;
}
inline void init(){
	Nil.h1 = Nil.val = Nil.size = 0;
	int len = 1, i;
	while(!isalpha(*tmp = getchar()));
	while(isalpha(tmp[len] = getchar()))++len;
	getd(M);
	const int m = min(M + len, maxn - 1);
	*pow1 = 1;
	for(i = 1;i <= m;++i)
		pow1[i] = pow1[i-1]*p1;
	Root = newT(tmp, len);
}
inline bool check(int x, int y, int len){
	Splay *t;
	ull h11, h21;
	if(x == 1){
		find(Root, len + 1);
		t = Root->son[0];
	}
	else{
		find(Root, x - 1);
		find(Root->son[1], len + 1);
		t = Root->son[1]->son[0];
	}
	h11 = t->h1;
	
	find(Root, y - 1);
	if(len == Root->son[1]->size)t = Root->son[1];
	else{
		find(Root->son[1], len + 1);
		t = Root->son[1]->son[0];
	}
	h21 = t->h1;
	if(h11 != h21)return 0;
	return 1;
}
inline void Query(){
	int l = 1, r, x, y, mid;
	getd(x), getd(y);
	if(x > y)x ^= y ^= x ^= y;
	r = Root->size - y + 1;
	if(x == y){
		printf("%d", r);
		if(M)putchar('\n');
		return;
	}
	while(l <= r){
		mid = (l + r) >> 1;
		if(check(x, y, mid))l = mid + 1;
		else r = mid - 1;
	}
	printf("%d", r);
	if(M)putchar('\n');
}
inline void Change(){
	int x, d;
	getd(x);while(!isalpha(d = getchar()));d -= 'a';
	find(Root, x);
	Root->val = d;
	Root->update();
}
inline void Insert(){
	int x, d;
	getd(x);while(!isalpha(d = getchar()));
	Splay *t = Pool[iter++].init(d - 'a');
	if(!x){
		t->son[1] = Root;
		Root = t;
		Root->update();
		return;
	}
	find(Root, x);
	t->son[1] = Root->son[1];Root->son[1] = t;
	t->update(); Root->update();
}
int main(){
	#if defined DEBUG
	freopen("test", "r", stdin);
	freopen("out.txt", "w", stdout);
	#else
	freopen("bzoj_1014.in", "r", stdin);
	freopen("bzoj_1014.out", "w", stdout);
	#endif
	int opt;
	init();
	while(M--){
		while(!isalpha(opt = getchar()));
		if(opt == 'Q'){
			Query();
		}
		else if(opt == 'R')Change();
		else Insert();
	}
	#if defined DEBUG
	cout << endl<< (double)clock() / CLOCKS_PER_SEC << " sec" << endl;
	#endif
	return 0;
}