首页 > 代码库 > [BZOJ 1014][JSOI2008]火星人prefix（Splay+二分+hash）
[BZOJ 1014][JSOI2008]火星人prefix（Splay+二分+hash）
Description
火星人最近研究了一种操作：求一个字串两个后缀的公共前缀。比方说，有这样一个字符串：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函数的值。
Solution
看到LongestComonQianzhui2333手动滑稽
如果不是很了解的话建议阅读《算法竞赛入门经典训练指南》3.4.3基于哈希值的LCP算法
用Splay维护一下
t[x].hash=t[lc(x)].hash+(t[x].val-‘a‘)*base[t[lc(x)].siz]+t[rc(x)].hash*base[t[lc(x)].siz+1]
#include<iostream>#include<cstdio>#include<cstring>#include<cstdlib>#define MAXN 100005#define lc(x) t[x].ch[0]#define rc(x) t[x].ch[1]#define Min(a,b) (a<b?a:b)using namespace std;int m,root,siz;char s[MAXN];unsigned long long base[MAXN];struct Node{ int ch[2],father,siz; unsigned long long hash; char val; Node(){ch[0]=ch[1]=father=siz=hash=0;}}t[MAXN];int Read(){ int x=0,f=1;char c=getchar(); while(c<‘0‘||c>‘9‘){ if(c==‘-‘)f=-1;c=getchar(); } while(c>=‘0‘&&c<=‘9‘){ x=x*10+c-‘0‘;c=getchar(); } return x*f;}void Update(int x){ t[x].siz=t[lc(x)].siz+t[rc(x)].siz+1; t[x].hash=(t[x].val-‘a‘)*base[t[lc(x)].siz]; t[x].hash+=t[lc(x)].hash+t[rc(x)].hash*base[t[lc(x)].siz+1];}void Rotate(int x,int &k){ int y=t[x].father; int z=t[y].father; int p=(t[y].ch[0]==x)?0:1; if(y==k)k=x; else { if(t[z].ch[0]==y)t[z].ch[0]=x; else t[z].ch[1]=x; } t[x].father=z; t[y].ch[p]=t[x].ch[p^1]; t[t[x].ch[p^1]].father=y; t[x].ch[p^1]=y; t[y].father=x; Update(y);Update(x);}void Splay(int x,int &k){ while(x!=k) { int y=t[x].father; int z=t[y].father; if(y!=k) { if((t[y].ch[0]==x)^(t[z].ch[0]==y)) Rotate(x,k); else Rotate(y,k); } Rotate(x,k); }}int Build(int l,int r,int f){ if(l>r)return 0; int now=(l+r)>>1; t[now].father=f; t[now].val=s[now]; t[now].ch[0]=Build(l,now-1,now); t[now].ch[1]=Build(now+1,r,now); Update(now); return now;}int Find(int x,int k){ if(!x)return 0; if(t[lc(x)].siz>=k)return Find(lc(x),k); if(t[lc(x)].siz+1<k)return Find(rc(x),k-t[lc(x)].siz-1); return x;}int check(int x,int y){ int a=Find(root,x),b=Find(root,y+2); Splay(a,root);Splay(b,rc(root)); return t[lc(rc(root))].hash;}void Query(int x,int y){ int l=1,r=Min(siz-x,siz-y)-1,ans=0; while(l<=r) { int mid=(l+r)>>1; if(check(x,x+mid-1)==check(y,y+mid-1)) ans=mid,l=mid+1; else r=mid-1; } printf("%d\n",ans);}void Change(int x,char d){ int a=Find(root,x+1); Splay(a,root); t[a].val=d;Update(a);}void Insert(int x,char d){ int a=Find(root,x+1),b=Find(root,x+2); Splay(a,root);Splay(b,rc(root)); siz++;t[rc(root)].ch[0]=siz; t[siz].val=d,t[siz].father=rc(root); Update(siz);Update(rc(root));Update(root);}int main(){ base[0]=1; for(int i=1;i<MAXN;i++)base[i]=base[i-1]*27; scanf("%s",s+2); siz=strlen(s+2)+2; s[1]=s[siz]=0; m=Read(); root=Build(1,siz,0); for(int i=1;i<=m;i++) { char opt,d;int x,y; opt=getchar(); while(opt<‘A‘||opt>‘Z‘)opt=getchar(); switch(opt) { case ‘Q‘: x=Read();y=Read(); Query(x,y); break; case ‘R‘: x=Read(); d=getchar();while(d<‘a‘||d>‘z‘)d=getchar(); Change(x,d); break; case ‘I‘: x=Read(); d=getchar();while(d<‘a‘||d>‘z‘)d=getchar(); Insert(x,d); break; } } return 0;}
[BZOJ 1014][JSOI2008]火星人prefix（Splay+二分+hash）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。