BZOJ 1014 JSOI 2008 火星人prefix Splay維護字符串Hash + 二分

BZOJ 1014 JSOI 2008 火星人prefix Splay維護字符串Hash + 二分

題目大意：定義LCQ為從x,y分別開始，有多長完全一樣。維護數據結構，給出xy，求出LCQ。此外還有修改和插入字符。

思路：LCQ一定是Hash＋二分，那麼插入和修改呢，當然就是用Splay維護了。Splay上的每個節點存當前位置的字符，和它和整個子樹的Hash值，重要是PushUp函數。除了維護子樹大小，還需要維護Hash值。

與正常計算Hash值的方法一樣，更新的根節點的Hash值可以表示為 Hash = ls->Hash + 27 ^ ls->size * Hash(root) + 27 ^ (ls->size + 1) * rs->Hash

詳見代碼。

CODE；

#include 
#include 
#include 
#include 
#define MAX 100010
using namespace std;

unsigned long long power[MAX];

struct Complex{
	char c;
	int size;
	unsigned long long hash;
	Complex *son[2],*father;

	void Combine(Complex *a,bool dir) {
		son[dir] = a;
		a->father = this;
	}
	bool Check() {
		return father->son[1] == this;
	}
	void PushUp() {
		size = son[0]->size + son[1]->size + 1;
        hash = son[0]->hash + (c - 'a' + 1) * power[son[0]->size] + son[1]->hash * power[son[0]->size + 1];
	}
}*nil = new Complex,*root;

char s[MAX];
int asks;

void Pretreatment();

Complex *BuildTree(int l,int r);
Complex *NewComplex(char _);
Complex *Kth(Complex *a,int k);

inline void Rotate(Complex *a,bool dir);
inline void Splay(Complex *a,Complex *aim);
inline void SplaySeg(int x,int y);

int main()
{
	Pretreatment();
	scanf("%s",s + 1);
    int length = (int)strlen(s + 1);
	root = BuildTree(0,length + 1);
	root->father = nil;
	cin >> asks;
	for(int x,y,i = 1;i <= asks; ++i) {
		scanf("%s",s);
		if(s[0] == 'Q') {
			scanf("%d%d",&x,&y);
			if(x > y)	swap(x,y);
			int l = 0,r = root->size - 2 - y + 1,ans = 0;
			while(l <= r) {
				int mid = (l + r) >> 1;
				SplaySeg(x,x + mid - 1);
				unsigned long long hash1 = root->son[1]->son[0]->hash;
				SplaySeg(y,y + mid - 1);
				unsigned long long hash2 = root->son[1]->son[0]->hash;
				if(hash1 == hash2)
					ans = mid,l = mid + 1;
				else	r = mid - 1;
			}
			printf("%d\n",ans);
		}
		else if(s[0] == 'R') {
			scanf("%d%s",&x,s);
			Splay(Kth(root,x + 1),nil);
			root->c = s[0];
			root->PushUp();
		}
		else {
			scanf("%d%s",&x,s);
			Splay(Kth(root,x + 1),nil);
			Splay(Kth(root,x + 2),root);
			root->son[1]->Combine(NewComplex(s[0]),false);
			root->son[1]->PushUp();
			root->PushUp();
		}
	}
	return 0;
}

void Pretreatment()
{
	nil->son[0] = nil->son[1] = nil->father = nil;
	nil->hash = 0;
	power[0] = 1;
	for(int i = 1;i < MAX; ++i)
		power[i] = power[i - 1] * 27;
}

Complex *BuildTree(int l,int r)
{
	if(l > r)	return nil;
	int mid = (l + r) >> 1;
	Complex *re = NewComplex(s[mid]);
	re->Combine(BuildTree(l,mid - 1),false);
	re->Combine(BuildTree(mid + 1,r),true);
	re->PushUp();
	return re;
}
Complex *NewComplex(char _) 
{
	Complex *re = new Complex();
	re->c = _;
	re->son[0] = re->son[1] = nil;
	re->hash = _ - 'a' + 1;
	re->size = 1;
	return re;
}

Complex *Kth(Complex *a,int k)
{
	if(k <= a->son[0]->size)	return Kth(a->son[0],k);
	k -= a->son[0]->size;
	if(k == 1)	return a;
	return Kth(a->son[1],k - 1);
}

inline void Rotate(Complex *a,bool dir)
{
	Complex *f = a->father;
	f->son[!dir] = a->son[dir];
	f->son[!dir]->father = f;
	a->son[dir] = f;
	a->father = f->father;
	f->father->son[f->Check()] = a;
	f->father = a;
	f->PushUp();
	if(root == f)	root = a;
}

inline void Splay(Complex *a,Complex *aim)
{
	while(a->father != aim) {
		if(a->father->father == aim)
			Rotate(a,!a->Check());
		else if(!a->father->Check()) {
			if(!a->Check())
				Rotate(a->father,true),Rotate(a,true);
			else	Rotate(a,false),Rotate(a,true);
		}
		else {
			if(a->Check())
				Rotate(a->father,false),Rotate(a,false);
			else	Rotate(a,true),Rotate(a,false);
		}
	}
	a->PushUp();
}

inline void SplaySeg(int x,int y)
{
	x++,y++;
	Splay(Kth(root,x - 1),nil);
	Splay(Kth(root,y + 1),root);
}