招聘网站入职分析表怎么做,网站关键字挖掘,300个吉祥公司取名大全,北京进入紧急状态正题
题目链接:https://www.luogu.com.cn/problem/P4036 题目大意
一个字符串要求支持
插入一个字符修改一个字符询问两个后缀的最长公共前缀。 解题思路
如果不考虑修改我们可以用二分hashhashhash解决该问题#xff0c;但是涉及到修改和插入我们考虑用SplaySplaySplay维…正题
题目链接:https://www.luogu.com.cn/problem/P4036 题目大意
一个字符串要求支持
插入一个字符修改一个字符询问两个后缀的最长公共前缀。 解题思路
如果不考虑修改我们可以用二分hashhashhash解决该问题但是涉及到修改和插入我们考虑用SplaySplaySplay维护hashhashhash值。
合并时使用hashhashl∗psizr1val∗psizrhashrhashhash_l*p^{siz_r1}val*p^{siz_r}hash_rhashhashl∗psizr1val∗psizrhashr进行合并即可。 codecodecode
#includecstdio
#includecstring
#includealgorithm
#define ull unsigned long long
using namespace std;
const int N2e510;
const ull base131;
struct node{int siz;ull val,hash;
}a[N];
int n,root,tot,m;
int t[N][2],fa[N];
char s[N];
ull p[N];
bool Direct(int x)
{return t[fa[x]][1]x;}
void Merge(int x){a[x].siza[t[x][0]].siza[t[x][1]].siz1;a[x].hashp[a[t[x][1]].siz1]*a[t[x][0]].hashp[a[t[x][1]].siz]*a[x].vala[t[x][1]].hash;
}
void Connect(int x,int y,int dir)
{t[x][dir]y;fa[y]x;}
void Rotate(int x){int yfa[x],rootfa[fa[x]];int ysDirect(x),rsDirect(y);int zt[x][ys^1];Connect(y,z,ys);Connect(x,y,ys^1);Connect(root,x,rs);Merge(y);Merge(x);return;
}
void Splay(int x,int f)
{while(fa[x]!f){int upfa[x];if(fa[up]f) Rotate(x);else if(Direct(x)Direct(up))Rotate(up),Rotate(x);else Rotate(x),Rotate(x); }return;
}
int Find(int x,int k)
{if(a[t[x][0]].sizk) return Find(t[x][0],k);if(a[t[x][0]].siz1k) return x;return Find(t[x][1],k-a[t[x][0]].siz-1);
}
int Split(int l,int r)
{int xFind(root,l),yFind(root,r2);Splay(x,0);Splay(y,x);rootx;return t[y][0];
}
ull ValSeq(int x,int y)
{return a[Split(x,y)].hash;
}
int main()
{scanf(%s,s1);nstrlen(s1);a[1].sizp[0]1;for(int i1;iN;i)p[i]p[i-1]*base;for(int i1;in;i){a[i1].vals[i]-a1;fa[i]i1;t[i1][0]i;Merge(i1);}fa[n1]n2;t[n2][0]n1;Merge(n2);roottotn2;scanf(%d,m);while(m--){char op[2];scanf(%s,op);if(op[0]Q){int x,y;scanf(%d%d,x,y);int l0,rmin(n-x,n-y);while(lr){int mid(lr)/2;if(ValSeq(x,xmid)ValSeq(y,ymid)) lmid1;else rmid-1;}printf(%d\n,r1);}if(op[0]R){int x;char c[2];scanf(%d%s,x,c);int kSplit(x,x);a[k].vala[k].hashc[0]-a1;Splay(k,0);rootk;}if(op[0]I){int x;char c[2];scanf(%d%s,x,c);x;int lFind(root,x),rFind(root,x1);Splay(l,0);Splay(r,l);n;fa[tot]r;t[r][0]tot;a[tot].siz1;a[tot].vala[tot].hashc[0]-a1;Splay(tot,0);roottot;}}
}
