SP3109 STRLCP - Longest Common Prefix 题解
某省某年省选原题出处，看来 CCF 出原题这事由来已久。
简化题意
- 让你维护一个字符串序列。
- 支持单点修改。
- 支持单点插入。
- 支持询问两个子串的最长公共前缀。
解法
本篇题解前置芝士：无旋 Treap（FHQ Treap），哈希，二分。如果有不会的请自行查找资料学习。
如果没有单点插入操作，我们可以考虑使用线段树维护区间哈希值（我不会后缀自动机）。求最长公共前缀时可以二分最长公共前缀的长度，这里记作 $mid$，判断两个字符串前 $mid$ 个字符是否相同（即哈希值相等），如果相同则证明答案不小于 $mid$，将二分范围向右侧缩小，如果不相同则证明答案小于 $mid$，将二分范围向左缩小。
为什么这题不能用普通线段树呢？因为单点插入操作会改变序列长度，就会改变线段树中父亲与儿子的关系。
那有没有能同时支持动态维护序列和区间信息的数据结构呢？有，平衡树可以动态维护序列。相信大家都会平衡树的基本操作了，这里只有合并区间信息这里和模板题不一样。所以我只讲如何合并区间信息。
先看线段树是如何合并区间哈希值的。
注意到平衡树的性质，根节点表示的点在左右子树表示的区间的中间。所以类似于线段树的区间合并，平衡树的区间合并是三个区间的合并。
查询 $[l,r]$ 区间的哈希值时可以将平衡树分裂成 $[1,l-1],[l,r],[r+1,L]$ 三棵平衡树，查询后再将三棵平衡树合并即可。$L$ 表示当前序列的长度。
综上，平衡树的时间复杂度是 $\mathcal{O}((L + c) \log L + q \log^2 L)$，分别是建树、修改、查询的时间复杂度，其中 $q$ 表示操作中查询次数，$c$ 表示操作中修改次数。
代码
#include<bits/stdc++.h>
namespace fast_IO
{
/**
* 快读快写
*/
};
using namespace fast_IO;
const int base=131;
int t,n,m,l,r,mid,ans;
char op,ch;
unsigned int pw[100010];
std::string st;
struct fhq_node
{
int w,siz;
unsigned int val,has;
fhq_node *lc,*rc;
inline fhq_node(unsigned int val)
{
this->val=has=val,w=rand(),siz=1,lc=rc=nullptr;
}
inline void pushup()
{
siz=(lc==nullptr?0:lc->siz)+(rc==nullptr?0:rc->siz)+1;
if(lc==nullptr && rc==nullptr) has=val;
else if(lc==nullptr) has=val*pw[rc->siz]+rc->has;
else if(rc==nullptr) has=lc->has*pw[1]+val;
else has=lc->has*pw[rc->siz+1]+val*pw[rc->siz]+rc->has;
}
};
class fhq_treap
{
private:
fhq_node *root;
inline fhq_node *merge(fhq_node *l,fhq_node *r)
{
if(l==nullptr) return r;
if(r==nullptr) return l;
if(l->w<r->w)
{
l->rc=merge(l->rc,r),l->pushup();
return l;
}else
{
r->lc=merge(l,r->lc),r->pushup();
return r;
}
}
inline std::pair<fhq_node *,fhq_node *> split(fhq_node *rt,const int &k)
{
std::pair<fhq_node *,fhq_node *> ret;
if(rt==nullptr) return std::make_pair(nullptr,nullptr);
int left=rt->lc==nullptr?0:rt->lc->siz;
if(k<=left) ret=split(rt->lc,k),rt->lc=ret.second,rt->pushup(),ret.second=rt;
else ret=split(rt->rc,k-left-1),rt->rc=ret.first,rt->pushup(),ret.first=rt;
return ret;
}
inline void clear(fhq_node *rt)
{
if(rt==nullptr) return;
if(rt->lc!=nullptr) clear(rt->lc);
if(rt->rc!=nullptr) clear(rt->rc);
delete rt;
}
public:
inline int getsiz()
{
return root->siz;
}
inline void clear()
{
clear(root),root=nullptr;
}
inline void fix(const int &pos,const unsigned int val)
{
std::pair<fhq_node *,fhq_node *> a,b;
a=split(root,pos),b=split(a.first,pos-1);
b.second->val=b.second->has=val,root=merge(merge(b.first,b.second),a.second);
}
inline void insert(const int &pos,const unsigned int val)
{
fhq_node *rt=new fhq_node(val);
std::pair<fhq_node *,fhq_node *> a;
a=split(root,pos),root=merge(merge(a.first,rt),a.second);
}
inline unsigned int ask(const int &L,const int &R)
{
std::pair<fhq_node *,fhq_node *> a,b;
a=split(root,R),b=split(a.first,L-1);
unsigned int ret=b.second->has;
root=merge(merge(b.first,b.second),a.second);
return ret;
}
};
fhq_treap tree;
int main()
{
srand(time(0)),pw[0]=1;
for(int i=1;i<=100001;i++) pw[i]=pw[i-1]*base;
in>>t;
while(t--)
{
in>>st>>m,st="#"+st,n=st.size()-1,tree.clear();
for(int i=1;i<=n;i++) tree.insert(i,st[i]-'a'+1);
for(int i=1,x,y;i<=m;i++)
{
in>>op>>x;
if(op=='Q')
{
in>>y;
if(x>y) std::swap(x,y);
l=1,r=tree.getsiz()-y+1,ans=0;
while(l<=r)
{
mid=(l+r)/2;
if(tree.ask(x,x+mid-1)==tree.ask(y,y+mid-1)) ans=mid,l=mid+1;
else r=mid-1;
}
out<<ans<<'\n';
}else if(op=='R') in>>ch,tree.fix(x,ch-'a'+1);
else in>>ch,tree.insert(x,ch-'a'+1);
}
}
fwrite(Ouf,1,p3-Ouf,stdout),fflush(stdout);
return 0;
}
