【BZOJ1014】火星人（Splay，哈希）

题面

BZOJ

题解

要动态维护这个串，一脸的平衡树。

那么用\(Splay\)维护这个哈希值就好了。

每次计算答案的时候二分+Splay计算区间哈希值，

时间复杂度\(O(nlog^2n)\)

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<set>

#include<map>

#include<vector>

#include<queue>

using namespace std;

#define ull unsigned long long

#define ll long long

#define RG register

#define MAX 111111

#define ls (t[x].ch[0])

#define rs (t[x].ch[1])

const int base=2333;

inline int read()

{

    RG int x=0,t=1;RG char ch=getchar();

    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

    if(ch=='-')t=-1,ch=getchar();

    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

    return x*t;

}

char ch[MAX];

ull pw[MAX];

int root,tot;

struct Node

{

	int ch[2],ff,size,len;

	ull v,Hash;

}t[MAX];

void pushup(int x)

{

	t[x].size=t[ls].size+t[rs].size+1;

	t[x].len=t[ls].len+t[rs].len+(x>2);

	t[x].Hash=(t[ls].Hash*base+t[x].v)*pw[t[rs].len]+t[rs].Hash;

}

void rotate(int x)

{

	int y=t[x].ff,z=t[y].ff;

	int k=t[y].ch[1]==x;

	t[z].ch[t[z].ch[1]==y]=x;t[x].ff=z;

	t[y].ch[k]=t[x].ch[k^1];t[t[x].ch[k^1]].ff=y;

	t[x].ch[k^1]=y;t[y].ff=x;

	pushup(y);

}

void Splay(int x,int goal)

{

	while(t[x].ff!=goal)

	{

		int y=t[x].ff,z=t[y].ff;

		if(z!=goal)

			(t[z].ch[0]==y)^(t[y].ch[0]==x)?rotate(x):rotate(y);

		rotate(x);

	}

	if(!goal)root=x;pushup(x);

}

int Kth(int k)

{

	int x=root;

	while(233)

	{

		if(t[ls].size+1==k)return x;

		if(t[ls].size+1<k)k-=t[ls].size+1,x=rs;

		else x=ls;

	}

}

ull Hash(int l,int len)

{

	int L=Kth(l),R=Kth(l+len+1);

	Splay(L,0);Splay(R,L);

	return t[t[R].ch[0]].Hash;

}

int LCQ(int x,int y)

{

	int l=0,r=tot-max(x,y)-1,ret=0;

	while(l<=r)

	{

		int mid=(l+r)>>1;

		if(Hash(x,mid)==Hash(y,mid))l=mid+1,ret=mid;

		else r=mid-1;

	}

	return ret;

}

void insert(int x,int v)

{

	int L=Kth(x+1),R=Kth(x+2);

	Splay(L,0);Splay(R,L);

	t[++tot].v=v;t[R].ch[0]=tot;

	t[tot].ff=R;Splay(tot,0);

}

void Modify(int x,int v)

{

	int L=Kth(x),R=Kth(x+2);

	Splay(L,0);Splay(R,L);

	t[t[R].ch[0]].v=v;pushup(t[R].ch[0]);

	pushup(R);pushup(L);

}

int main()

{

	pw[0]=1;for(int i=1;i<MAX;++i)pw[i]=pw[i-1]*base;

	scanf("%s",ch+1);

	t[1].ch[1]=2;t[2].ff=1;tot=2;root=1;pushup(2);pushup(1);

	for(int i=1,l=strlen(ch+1);i<=l;++i)insert(i-1,ch[i]);

	int Q=read(),x,y;

	while(Q--)

	{

		scanf("%s",ch);

		if(ch[0]=='Q')printf("%d\n",LCQ(read(),read()));

		else if(ch[0]=='R'){x=read();scanf("%s",ch);y=ch[0];Modify(x,y);}

		else{x=read();scanf("%s",ch);y=ch[0];insert(x,y);}

	}

	return 0;

}