$bzoj1014-JSOI2008$ 火星人$prefix$ $splay$ $hash$

题面描述
- 火星人最近研究了一种操作：求一个字串两个后缀的公共前缀。比方说，有这样一个字符串：$madamimadam$，我们将这个字符串的各个字符予以标号：
  - 序号 1 2 3 4 5 6 7 8 9 10 11
  - 字符 m a d a m i m a d a m
- 现在，火星人定义了一个函数$LCQ(x, y)$，表示：该字符串中第$x$个字符开始的字串，与该字符串中第$y$个字符开始的字串，两个字串的公共前缀的长度。比方说，$LCQ(1, 7) = 5, LCQ(2, 10) = 1, LCQ(4, 7) = 0$ 在研究$LCQ$函数的过程中，火星人发现了这样的一个关联：如果把该字符串的所有后缀排好序，就可以很快地求出$LCQ$函数的值；同样，如果求出了$LCQ$函数的值，也可以很快地将该字符串的后缀排好序。尽管火星人聪明地找到了求取$LCQ$函数的快速算法，但不甘心认输的地球人又给火星人出了个难题：在求取$LCQ$函数的同时，还可以改变字符串本身。具体地说，可以更改字符串中某一个字符的值，也可以在字符串中的某一个位置插入一个字符。地球人想考验一下，在如此复杂的问题中，火星人是否还能够做到很快地求取$LCQ$函数的值。
输入格式
- 第一行给出初始的字符串。第二行是一个非负整数$M$，表示操作的个数。接下来的$M$行，每行描述一个操作。操作有$3$种，如下所示
  - 询问
    - 语法：$Q\ x\ y$，$x,y$均为正整数。
    - 功能：计算$LCQ(x,y)$限制：$1<=x,y<=当前字符串长度$。
  - 修改
    - 语法：$R\ x\ d$，$x$是正整数，$d$是字符。
    - 功能：将字符串中第$x$个数修改为字符$d$。限制：$x$不超过当前字符串长度。
  - 插入：
    - 语法：$I\ x\ d$，$x$是非负整数，$d$是字符。
    - 功能：在字符串第$x$个字符之后插入字符$d$，如果$x=0$，则在字符串开头插入。
    - 限制：$x$不超过当前字符串长度
输出格式
- 对于输入文件中每一个询问操作，你都应该输出对应的答案。一个答案一行。
题解
- 比较水的题，码量巨大，还卡常(bzoj)，我最后是开了手动O3才过的.....
- 对于没有修改和插入操作的题目，一般主流有两种做法
  - 建出给定串的后缀数组或后缀自动机，求解
  - 用字符串$hash$，通过二分公共长度$ans$，求解
- 但因为题目中出现修改和插入操作，而后缀数组和后缀自动机都是静态的，因此无法维护动态插入、修改
- 因此我们可以用的就只剩下字符串 $hash$了，那么问题相当于转化为动态维护 $hash$序列
  - 在中间某一位 $pos$后插入一个数
    - 这里我当时写的时候不小心把$ins(pos)$写成在$pos$前加一个数，因此之后的插入操作被我写成 $ins(pos+1)$ 在$pos+1$前加一个数
  - 修改其中一个数
- 这些操作可以完全被$Splay$胜任
注意
- 初始化$p[]$一定要算到$p[10^5+5*10^4]$上，不然之后插入字符的时候就会爆炸
- 注意常数优化
备注
- 我在代码里附了两种算$hash$的方法
  - 用$splay$维护前缀$hash$，在用普通$hash$的方法计算$hash$值
  - 直接用$splay$维护这段子串的$hash$值

#pragma GCC optimize(3)

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

typedef long long ll;

#define ri register

#define il inline

const int inf=1e9;

const int MAXN=1e5+5e4+5;

const int mod=9875321;

int n,m,M,rt;

struct tnode{

	int dat,val,fa,sz;

	int ch[3];

} t[MAXN];

int p[MAXN];

char s[MAXN];

il int newnode(int val,int fa,int cl,int cr){

	t[++M]=(tnode){val,val,fa,1};

	t[M].ch[0]=cl; t[M].ch[1]=cr;

	return M;

}

il void update(int u){

	if (!u) return;

	t[0].dat=t[0].sz=0;

	int cl=t[u].ch[0],cr=t[u].ch[1];

	int szl=t[cl].sz,szr=t[cr].sz;

	t[u].sz=szl+szr+1;

	t[u].dat=((ll)t[cl].dat*p[szr+1]%mod+(ll)p[szr]*t[u].val%mod+t[cr].dat)%mod;

}

il void rotate(int u){

	int f1=t[u].fa;

	int f2=t[f1].fa;

	int dir1=t[f1].ch[1]==u;

	int dir2=t[f2].ch[1]==f1;

	int sn=t[u].ch[dir1^1];

	t[sn].fa=f1; t[f1].ch[dir1]=sn;

	t[f1].fa=u; t[u].ch[dir1^1]=f1;

	t[u].fa=f2; t[f2].ch[dir2]=u;

	update(f1); update(u);

}

il void splay(int u,int go){

	if (u==go) return;

	while (t[u].fa!=go){

		int f1=t[u].fa;

		int f2=t[f1].fa;

		int dir1=t[f1].ch[1]==u;

		int dir2=t[f2].ch[1]==f1;

		if (f2==go){

			rotate(u);

			break;

		}

		if (dir1==dir2) rotate(f1);

		else rotate(u);

		rotate(u);

	}

	if (go==0) rt=u;

}

int num(int u,int rk){

	int cl=t[u].ch[0],cr=t[u].ch[1];

	int szl=t[cl].sz,szr=t[cr].sz;

	if (cl==0&&cr==0) return u;

	if (rk<=szl) return num(cl,rk);

	else if (rk>szl+1) return num(cr,rk-szl-1);

	else return u;

}

il void ins(int key,char c){

	int cdat=c-'a'+1;

	if (abs(key)>=inf) cdat=0;

	if (rt==0){

		rt=newnode(cdat,0,0,0);

		return;

	}

	splay(num(rt,key+1),0);

	int u=rt;

	int cl=t[u].ch[0];

	rt=newnode(cdat,0,cl,u);

	t[u].fa=rt; t[cl].fa=rt;

	t[u].ch[0]=0;

	update(u); update(rt);

}

/*int qry(int key){

	splay(num(rt,key+2),0);

//	cout<<__func__<<key<<" "<<(char)(t[rt].val+'a'-1)<<" "<<t[t[rt].ch[0]].dat<<endl;

	return t[t[rt].ch[0]].dat%mod;

}

bool check(int x,int y,int mid){

	int xr=x+mid-1,yr=y+mid-1;

	cout<<x<<" "<<xr<<" "<<y<<" "<<yr<<endl;

	if (xr>n||yr>n) return 0;

//	cout<<qry(xr)<<" "<<qry(x-1)<<endl;

	int ansx=(ll)((qry(xr)-(ll)qry(x-1)*p[mid]%mod)%mod+mod)%mod;

	int ansy=(ll)((qry(yr)-(ll)qry(y-1)*p[mid]%mod)%mod+mod)%mod;

	cout<<ansx<<" "<<ansy<<endl;

	return ansx==ansy;

}*/

il int qry(int l,int r){

	splay(num(rt,l),0);

	splay(num(rt,r+2),rt);

	return t[t[t[rt].ch[1]].ch[0]].dat%mod;

}

il bool check(int x,int y,int mid){

	int xr=x+mid-1,yr=y+mid-1;

	if (xr>n||yr>n) return 0;

	return qry(x,xr)==qry(y,yr);

}

il void solve(int x,int y){

	if (x==y){

		printf("%d\n",n-x+1);

		return;

	}

	int l=0,r=max(n-x+1,n-y+1)+1,mid;

//	cout<<__func__<<" "<<l<<" "<<r<<endl;

	while (l+1<r){

		mid=(l+r)>>1;

		if (check(x,y,mid)) l=mid;

		else r=mid;

	}

	printf("%d\n",l);

}

void prt(int u){

	int cl=t[u].ch[0],cr=t[u].ch[1];

	printf("id:%d c:%d dat:%d fa:%d cl:%d cr:%d\n",u,t[u].val,t[u].dat,t[u].fa,cl,cr);

	if (cl) prt(cl);

//	printf("%c",(char)t[u].val+'a'-1);

	if (cr) prt(cr);

}

int main(){

//	freopen("1014.in","r",stdin);

//	freopen("1014.out","w",stdout);

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

	n=strlen(s+1);

	p[0]=1;

	for (ri int i=1;i<=105000;i++) p[i]=(ll)p[i-1]*27%mod;

	ins(inf,'a'); ins(-inf,'a');

	for (ri int i=1;i<=n;i++) ins(i,s[i]);

//	prt(rt);cout<<endl;

	scanf("%d",&m);

	for (ri int i=1;i<=m;i++){

		char c=getchar(); while (c!='Q'&&c!='R'&&c!='I') c=getchar();

		int x; scanf("%d",&x);

		if (c=='Q'){

			int y; scanf("%d",&y);

			solve(x,y);

		}

		if (c=='R'){

			char y=getchar(); while (y<'a'||y>'z') y=getchar();

			splay(num(rt,x+1),0);

			t[rt].val=y-'a'+1;

			update(rt);

		}

		if (c=='I'){

			char y=getchar(); while (y<'a'||y>'z') y=getchar();

			ins(x+1,y);

			n++;

		}

//		prt(rt); cout<<endl;

	}

	fclose(stdin); fclose(stdout);

	return 0;

}

天助自助者

巴特西

$bzoj1014-JSOI2008$ 火星人$prefix$ $splay$ $hash$

最新文章

热门文章