【BZOJ1014】火星人

  splay+hash，splay维护区间hash值，查询的时候二分答案。

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
typedef long long LL;
using namespace std;
const int maxn=100010,p1=1000007,p2=1000009;
inline void readchar(char &ch) {while ((ch=getchar())==' ' || ch=='\n');}
inline void read(int &x) {char ch;while ((ch=getchar())<'0' || ch>'9');x=ch-'0';while ((ch=getchar())<='9' && ch>='0') x=x*10+ch-'0';}

char s[maxn];
int n;

struct Node
{
	Node *p,*c[2];
	int v,size,h1,h2;
	bool w() {return p->c[1]==this;}
}*root,*Null;

namespace Memory
{
	Node Mem[maxn],*Stack[maxn];
	int top;
	void Init() {for (int i=0;i<maxn;i++) Stack[i]=Mem+i;top=maxn;}
	Node* New_Node() {return Stack[--top];}
	void Delete_Node(Node *x) {Stack[top++]=x;}
}

int h1[maxn],h2[maxn];

struct Splay_Tree
{
	#define ls x->c[0]
	#define rs x->c[1]

	void Update(Node *x)
	{
		if (x==Null) return;
		x->size=ls->size+rs->size+1;
		x->h1=(ls->h1+1ll*x->v*h1[ls->size]+1ll*rs->h1*h1[ls->size+1])%p1;
		x->h2=(ls->h2+1ll*x->v*h2[ls->size]+1ll*rs->h2*h2[ls->size+1])%p2;
	}

	void Rotate(Node *x)
	{
		Node *p=x->p;
		bool w=x->w();
		x->c[!w]->p=p;p->p->c[p->w()]=x;
		p->c[w]=x->c[!w];x->c[!w]=p;
		x->p=p->p;p->p=x;
		Update(p);
		if (p==root) root=x;
	}

	void Splay(Node *x,Node *head)
	{
		while (x->p!=head)
		{
			if (x->p->p==head) Rotate(x);
			else if (x->w()==x->p->w()) Rotate(x->p),Rotate(x);
			else Rotate(x),Rotate(x);
		}
		Update(x);
	}

	Node* Select(int kth)
	{
		Node *x=root;
		while (kth)
		{
			int lsize=ls->size;
			if (lsize+1==kth) return x;
			if (lsize<kth) kth-=lsize+1,x=rs;
			else x=ls;
		}
		return x;
	}
	
	Node* Get_Seq(int l,int r)
	{
		if (l==1 && r==n) return root;
		if (l==1) {Splay(Select(r+1),Null);return root->c[0];}
		if (r==n) {Splay(Select(l-1),Null);return root->c[1];}
		Splay(Select(l-1),Null);
		Splay(Select(r+1),root);
		return root->c[1]->c[0];
	}

	Node* New_Node(int v)
	{
		Node *x=Memory::New_Node();
		x->v=v;x->size=1;
		x->h1=x->h2=v;
		x->p=ls=rs=Null;
		return x;
	}

	Splay_Tree()
	{
		Memory::Init();
		Null=Memory::New_Node();
		Null->v=Null->size=Null->h1=Null->h2=0;
		Null->p=Null=Null->c[0]=Null->c[1]=Null;
		root=Null;
	}

	void Insert(int pos,int v)
	{
		Node *x=New_Node(v);
		if (pos==0)
		{
			Splay(Select(1),Null);
			root->c[0]=x;
			x->p=root;
			Update(root);
		}
		else if (pos==n)
		{
			Splay(Select(n),Null);
			root->c[1]=x;
			x->p=root;
			Update(root);
		}
		else
		{
			Splay(Select(pos),Null);
			Splay(Select(pos+1),root);
			root->c[1]->c[0]=x;
			x->p=root->c[1];
			Splay(x,Null);
		}
	}
	
	void Change(int pos,int v)
	{
		Node *x=Select(pos);
		x->v=v;
		Splay(x,Null);
	}

	Node* Make_Tree(int l,int r)
	{
		if (l>r) return Null;
		int mid=(l+r)>>1;
		Node *x=New_Node((int)s[mid]);
		ls=Make_Tree(l,mid-1);
		rs=Make_Tree(mid+1,r);
		if (ls!=Null) ls->p=x;
		if (rs!=Null) rs->p=x;
		Update(x);
		return x;
	}

	LL Hash_Val(int pos,int tot)
	{
		LL res=0;
		Node *x=Get_Seq(pos,pos+tot-1);
		res=x->h1*(LL)p2+x->h2;
		return res;
	}
}T;

int main()
{
	h1[0]=h2[0]=1;
	for (int i=1;i<maxn;i++) h1[i]=(h1[i-1]*257)%p1,h2[i]=(h2[i-1]*259)%p2;
	scanf("%s",s);
	n=strlen(s);
	root=T.Make_Tree(0,n-1);
	root->p=Null;
	int m;
	read(m);
	while (m--)
	{
		char ctr;
		readchar(ctr);
		if (ctr=='Q')
		{
			int x,y;
			read(x),read(y);
			int l=0,r=min(n+1-x,n+1-y),mid;
			while (l<r)
			{
				mid=(l+r+1)>>1;
				if (T.Hash_Val(x,mid)!=T.Hash_Val(y,mid)) r=mid-1;
				else l=mid;
			}
			printf("%d\n",l);
		}
		else if (ctr=='I')
		{
			int x;char ch;
			read(x);readchar(ch);
			T.Insert(x,(int)ch);
			n++;
		}
		else
		{
			int x;char ch;
			read(x);readchar(ch);
			T.Change(x,ch);
		}
	}
	return 0;
}