BZOJ 1014 [JSOI2008]火星人prefix

题目大意

请你维护一个字符串，支持：

1. 插入一个字符
2. 更改一个字符
3. 查询该字符串以i位和j位为起始的最长公共前缀。

首先求字符串最长公共前缀之类的可以考虑使用二分+哈希来进行求解，时间复杂度$O(T \log N)$……

不对不对还需要支持更改!

考虑hash的性质——它可以区间合并。如果用数据结构维护的话发现好像时间复杂度是可过的！

因为需要动态在某一特定位置插入一个数并维护，所以我们考虑使用Splay.

我没有发现其实查询的两个端点不保证L<R，而我判断边界防止RE的时候使用的方法就只是判断R+mid是否超出边界，于是就各种RE......

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 500000
int siz[N+1],fa[N+1],c[2][N+1],rt,a,b,n,m;
char t[5],md[5],s[N+1];
unsigned long long bs[N+1],v[N+1];
inline void pushup(int pos)
{
	siz[pos]=siz[c[0][pos]]+siz[c[1][pos]]+1;
	v[pos]=v[c[0][pos]]*bs[siz[c[1][pos]]+1]+s[pos]*bs[siz[c[1][pos]]]+v[c[1][pos]];
}
inline void rotate(int &tg,int tx)
{
	int ty=fa[tx],tz=fa[ty],tl=(c[1][ty]==tx),tr=tl^1;
	if(tg==ty) tg=tx;
	else c[c[1][tz]==ty][tz]=tx;
	fa[tx]=tz,fa[ty]=tx;
	fa[c[tr][tx]]=ty,c[tl][ty]=c[tr][tx],c[tr][tx]=ty;
	pushup(ty),pushup(tx);
}
inline void splay(int &tg,int tx)
{
	while(tg!=tx)
	{
		int ty=fa[tx],tz=fa[ty];
		if(tg!=ty)
		{
			if((c[1][ty]==tx)^(c[1][tz]==ty)) rotate(tg,tx);
			else rotate(tg,ty);
		}
		rotate(tg,tx);
	}
}
int lookfor(int pos,int tg)
{
	if(tg<=siz[c[0][pos]]) return lookfor(c[0][pos],tg);
	if(tg>siz[c[0][pos]]+1) return lookfor(c[1][pos],tg-siz[c[0][pos]]-1);
	return pos;
}
unsigned long long query(int l,int r)
{
	splay(rt,lookfor(rt,l)),splay(c[1][rt],lookfor(rt,r+2));
	return v[c[0][c[1][rt]]];
}
inline int bisection()
{
	int l=0,r=siz[rt]-2,mid;
	while(l<r)
	{
		mid=(l+r)>>1;
		if(b+mid<=siz[rt]-2&&query(a,a+mid)==query(b,b+mid)) l=mid+1;
		else r=mid;
	}
	return l;
}
int build(int l,int r)
{
	if(l>r) return 0;
	int mid=(l+r)>>1;
	c[0][mid]=build(l,mid-1),fa[c[0][mid]]=mid;
	c[1][mid]=build(mid+1,r),fa[c[1][mid]]=mid;
	pushup(mid);
	return mid;
}
int main()
{
	bs[0]=1;
	for(int i=1;i<=100000;++i) bs[i]=bs[i-1]*131;
	scanf("%s%d",s+2,&m);
	n=strlen(s+2)+2;
	rt=build(1,n);
	while(m--)
	{
		scanf("%s",md);
		switch(md[0])
		{
			case 'Q':
			{
				scanf("%d%d",&a,&b);
				if(a>b) swap(a,b);
				printf("%d\n",bisection());
				break;
			}
			case 'R':
			{
				scanf("%d%s",&a,t);
				splay(rt,lookfor(rt,a)),splay(c[1][rt],lookfor(rt,a+2));
				s[c[0][c[1][rt]]]=v[c[0][c[1][rt]]]=t[0];
				pushup(c[1][rt]),pushup(rt);
				break;
			}
			case 'I':
			{
				scanf("%d%s",&a,t);
				splay(rt,lookfor(rt,a+1)),splay(c[1][rt],lookfor(rt,a+2));
				c[0][c[1][rt]]=++n,fa[n]=c[1][rt],s[n]=v[n]=t[0],siz[n]=1;
				pushup(c[1][rt]),pushup(rt);
				break;
			}
		}
	}
}