回头补字符串（从SAM开始）
# 题面
给定一个长度为 (n) 的 01 字符串 (S)，记以 (i) 位置结束的前缀为 (S[i])。
给定 (m) 组询问，每组询问给出 (l,r)，求
[max_{i,j}ig{operatorname{LCS}(S[i],S[j])mid i
eq jland lle i,jle rig}
]
数据规模：(n,mle 10^5)。
# 解析
考虑建出 SAM，记 SAM 上代表前缀 (i) 的节点为 (p_i)，则有 (operatorname{LCS}(S[i],S[j])) 为 parent 树上 (p_i,p_j) 的 LCA 代表的最长字符串长度。
由此分析以下两种做法。
- SOLUTION 1. 启发式合并
考虑在 parent 树上由子树向上合并。
用 set 维护出子树 (i) 中包含了哪些前缀，记这个集合为 (E_i)，合并只需将子节点 (v) 的 (E_v) 与父节点 (u) 的 (E_u) 合并后的结果赋给新的 (E_u) 即可。
通过启发式合并，每次暴力将较小的集合中的元素插入较大集合，可以做到 (mathcal{O}(nlog^2n))。
再考虑如何计算答案。当子节点 (v) 的信息合并到父节点 (u) 上时，考虑每对 ((i,j))：(iin E_v), (jin E_u)；(p_i,p_j) 的 LCA 就是点 (u)。
显然每对 ((i,j)) 的 LCS 可以贡献到满足 (lle min{i,j}< max{i,j}le r) 的询问 ((l,r))。
那么我们只需要合并时记录下三元组 ((i,j,x))，表示 (LCS(S[i],S[j])=x)。对询问离线，two-point + 树状数组 即可回答询问。
但是我们发现三元组的数量是 (mathcal{O}(n^2)) 的，不能接受。观察之前的过程，发现许多三元组是无用的——
在合并 (E_u,E_v) 时，对于每个 (iin E_u)，我们只需要找到 (E_v) 中 (i) 的 “前驱” 和 “后继” (j)。因为比前驱更小的 (j)，其能够贡献到的 ((l,r)) 的范围更小，比后继更大的 (j) 同理。
合并次数是 (mathcal{O}(nlog n))，于是三元组的数量也是 (mathcal{O}(nlog n))。
用 two-point + 树状数组，具体地：
- 将询问 ((l,r)) 挂在 (r)；
- 从左到右枚举右端点 (r_0)，枚举三元组 ((l_0,r_0,x_0))，更新 (l< l_0) 的询问的答案与 (x_0) 取 max；
- 因为取 max 不存在删除操作，也就不必要讨论树状数组无可减性的限制，只需树状数组维护后缀 max 即可回答挂在 (r) 的询问。
复杂度也是 (mathcal{O}(nlog^2n))。
- SOLUTION 2. LCT
同样对询问离线，将 ((l,r)) 挂在 (r) 处。
考虑一种求树上 LCA 的方法。求 (u,v) 的 LCA，可以将根到 (u) 的路径上打上 (u) 的标记，然后从 (v) 向上爬，找到第一个有 (u) 的标记的点，即为 LCA。
于是我们可以这样解决这个问题：
- 从左到右加入右端点 (r)；
- 从 (p_r) 开始向根爬，对路上找到的每个标记 (l)，同样记录三元组 ((l,r,x)) 表示 (LCS(S[i],S[j])=x)；
- 将 (p_r) 到根的路径打上 (r) 的标记。
但是显然一个点上会被盖很多标记，这样复杂度就不优了。
实际上我们只需要保留每个点上最大的标记，和 SOLUTION 1 一样的道理，因为与 (p_r) LCA 相同的 (p_l) 只有 (l) 最大的能够贡献到的询问是最多的。
因为我们是从小到大插入 (r)，保留最大的就相当于直接覆盖。
然后考虑如何实现这个过程，不妨观察一下……
这不是 LCT 的 access 操作吗？
所以直接用 LCT，就可以同时找到链上的标记，以及给链打标记了。
# 源代码
- 启发式合并
点击展开/折叠代码
/*Lucky_Glass*/
#include<set>
#include<vector>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
inline int rin(int &r){
int b=1,c=getchar();r=0;
while(c<'0' || '9'<c) b=c=='-'?-1:b,c=getchar();
while('0'<=c && c<='9') r=(r<<1)+(r<<3)+(c^'0'),c=getchar();
return r*=b;
}
const int N=1e5+10;
#define con(type) const type &
typedef set<int>::iterator iter;
struct Segment{
int le,ri,key;
Segment(){}
Segment(con(int)_le,con(int)_ri,con(int)_key):le(_le),ri(_ri),key(_key){}
}seg[N*20];
bool cmpSegment(con(Segment)u,con(Segment)v){return u.ri<v.ri;}
int nseg;
struct Node{
int nxt[2],len,fa;
inline int& operator [](con(int)i){return nxt[i];}
};
struct SamAuto{
int bin[N],setid[N<<1],idx[N<<1],ncnt,rt,lasnod;
Node nod[N<<1];
set<int> endpos[N<<1];
int newNode(con(int)_len){
int p=++ncnt;nod[p].len=_len;
return p;
}
void extend(con(int)c,con(int)id){
int p=lasnod,np=newNode(nod[p].len+1);
lasnod=np;
endpos[np].insert(id);
while(p && !nod[p][c]) nod[p][c]=np,p=nod[p].fa;
if(!p) nod[np].fa=rt;
else{
int q=nod[p][c];
if(nod[q].len==nod[p].len+1) nod[np].fa=q;
else{
int nq=newNode(0);
nod[nq]=nod[q],nod[nq].len=nod[p].len+1;
nod[q].fa=nod[np].fa=nq;
while(p && nod[p][c]==q) nod[p][c]=nq,p=nod[p].fa;
}
}
}
void build(char *str,con(int)len){
rt=lasnod=newNode(0);
for(int i=1;i<=len;i++) extend(str[i]-'0',i);
}
void solve(con(int)len){
for(int i=1;i<=ncnt;i++) bin[nod[i].len]++,setid[i]=i;
for(int i=1;i<=len;i++) bin[i]+=bin[i-1];
for(int i=1;i<=ncnt;i++) idx[bin[nod[i].len]--]=i;
for(int i=ncnt;i>1;i--){
int u=idx[i],uid=setid[u],fid=setid[nod[u].fa],key=nod[nod[u].fa].len;
if(endpos[uid].size()>endpos[fid].size()) swap(uid,fid);
for(iter it=endpos[uid].begin();it!=endpos[uid].end();it++){
iter tmp=endpos[fid].lower_bound(*it);
if(tmp!=endpos[fid].end()) seg[++nseg]=Segment(*it,*tmp,key);
if(tmp!=endpos[fid].begin()) tmp--,seg[++nseg]=Segment(*tmp,*it,key);
}
for(iter it=endpos[uid].begin();it!=endpos[uid].end();it++)
endpos[fid].insert(*it);
setid[nod[u].fa]=fid;
}
}
}sam;
struct TreeArray{
#define lowbit(x) ((x)&(-(x)))
int ary[N],siz;
void init(con(int)_siz){siz=_siz;}
void modify(con(int)pos,con(int)key){
for(int i=pos;i<=siz;i+=lowbit(i))
ary[i]=max(ary[i],key);
}
int query(con(int)pos){
int ret=0;
for(int i=pos;i;i-=lowbit(i))
ret=max(ret,ary[i]);
return ret;
}
#undef lowbit
}tary;
int n,m;
char str[N];
int ans[N];
vector< pair<int,int> > qry[N];
int main(){
// freopen("input.in","r",stdin);
rin(n),rin(m),scanf("%s",str+1);
sam.build(str,n);
sam.solve(n);
sort(seg+1,seg+1+nseg,cmpSegment);
// for(int i=1;i<=nseg;i++) printf("[%d,%d] = %d
",seg[i].le,seg[i].ri,seg[i].key);
for(int i=1,le,ri;i<=m;i++){
rin(le),rin(ri);
qry[ri].push_back(make_pair(le,i));
}
tary.init(n);
for(int i=1,pseg=1;i<=n;i++){
while(pseg<=nseg && seg[pseg].ri==i){
tary.modify(n-seg[pseg].le+1,seg[pseg].key);
pseg++;
}
for(int k=0,kk=(int)qry[i].size();k<kk;k++)
ans[qry[i][k].second]=tary.query(n-qry[i][k].first+1);
}
for(int i=1;i<=m;i++) printf("%d
",ans[i]);
return 0;
}
- LCT
点击展开/折叠代码
/*Lucky_Glass*/
#include<vector>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
inline int rin(int &r){
int b=1,c=getchar();r=0;
while(c<'0' || '9'<c) b=c=='-'?-1:b,c=getchar();
while('0'<=c && c<='9') r=(r<<1)+(r<<3)+(c^'0'),c=getchar();
return r*=b;
}
const int N=1e5+10;
#define con(type) const type &
struct TreeArray{
#define lowbit(x) ((x)&(-(x)))
int arr[N],siz;
void init(con(int)_siz){siz=_siz;}
void modify(con(int)pos,con(int)key){
for(int i=pos;i<=siz;i+=lowbit(i))
arr[i]=max(arr[i],key);
}
int query(con(int)pos){
int ret=0;
for(int i=pos;i;i-=lowbit(i)) ret=max(ret,arr[i]);
return ret;
}
#undef lowbit
}tary;
struct Node{
int nxt[2],len,fa;
inline int& operator [](con(int)i){return nxt[i];}
};
struct SamAuto{
Node nod[N<<1];
int lasnod,rt,ncnt,pos[N];
int newNode(con(int)_len){
int p=++ncnt;
nod[p].len=_len;
return p;
}
void extend(con(int)c,con(int)id){
int p=lasnod,np=newNode(nod[p].len+1);
pos[id]=lasnod=np;
while(p && !nod[p][c]) nod[p][c]=np,p=nod[p].fa;
if(!p) nod[np].fa=rt;
else{
int q=nod[p][c];
if(nod[q].len==nod[p].len+1) nod[np].fa=q;
else{
int nq=newNode(0);
nod[nq]=nod[q],nod[nq].len=nod[p].len+1;
nod[np].fa=nod[q].fa=nq;
while(p && nod[p][c]==q) nod[p][c]=nq,p=nod[p].fa;
}
}
}
void build(char *str,con(int)len){
rt=lasnod=newNode(0);
for(int i=1;i<=len;i++) extend(str[i]-'0',i);
}
int operator [](con(int)i){return pos[i];}
}sam;
namespace LCT{
struct SNode{
int nxt[2],fa,mx,lzy;
inline int& operator [](con(int)i){return nxt[i];}
}nod[N<<1];
void samToLCT(con(int)n){
for(int i=1;i<=n;i++)
nod[i].fa=sam.nod[i].fa;
}
bool ifRoot(con(int)u){return !nod[u].fa || (nod[nod[u].fa][0]!=u && nod[nod[u].fa][1]!=u);}
void setChild(con(int)u,con(int)v,con(int)d){
nod[u][d]=v;
if(v) nod[v].fa=u;
}
void update(con(int)u,con(int)key){
nod[u].mx=max(nod[u].mx,key);
nod[u].lzy=max(nod[u].lzy,key);
}
int dir(con(int)x){return nod[nod[x].fa][1]==x;}
void pushDown(con(int)u){
if(!nod[u].lzy) return;
if(nod[u][0]) update(nod[u][0],nod[u].lzy);
if(nod[u][1]) update(nod[u][1],nod[u].lzy);
nod[u].lzy=0;
}
void pushUp(con(int)u){nod[u].mx=max(nod[u].mx,max(nod[nod[u][0]].mx,nod[nod[u][1]].mx));}
void ina_rotate(con(int)x){
int y=nod[x].fa,d=dir(x);
pushDown(y),pushDown(x);
if(!ifRoot(y)) setChild(nod[y].fa,x,dir(y));
else nod[x].fa=nod[y].fa;
setChild(y,nod[x][!d],d);
setChild(x,y,!d);
pushUp(y),pushUp(x);
}
void splay(int x){
static int stk[N<<1];
int nstk=0,tmp=x;
while(!ifRoot(tmp))
stk[++nstk]=tmp,tmp=nod[tmp].fa;
stk[++nstk]=tmp;
while(nstk) pushDown(stk[nstk--]);
while(!ifRoot(x)){
int y=nod[x].fa;
if(ifRoot(y)) ina_rotate(x);
else{
if(dir(x)==dir(y)) ina_rotate(y);
else ina_rotate(x);
ina_rotate(x);
}
}
pushUp(x);
}
void access(int x,con(int)tag,con(int)n){
int y;
for(y=0;x;y=x,x=nod[x].fa){
splay(x);
setChild(x,y,1);
tary.modify(n-nod[x].mx+1,sam.nod[x].len);
}
update(y,tag);
}
}
int n,m;
char str[N];
int ans[N];
vector< pair<int,int> > qry[N];
int main(){
// freopen("input.in","r",stdin);
rin(n),rin(m),scanf("%s",str+1);
for(int i=1,l,r;i<=m;i++){
rin(l),rin(r);
qry[r].push_back(make_pair(l,i));
}
tary.init(n);
sam.build(str,n);
LCT::samToLCT(sam.ncnt);
for(int i=1;i<=n;i++){
LCT::access(sam[i],i,n);
for(int k=0,kk=(int)qry[i].size();k<kk;k++)
ans[qry[i][k].second]=tary.query(n-qry[i][k].first+1);
}
for(int i=1;i<=m;i++) printf("%d
",ans[i]);
return 0;
}
THE END
Thanks for reading!
（天地虽大）水中明月又一片
（其化均也）心上尘埃只一叶
（万物虽多）提指拈花却一线
（其治一也）恍然一念间
（四达通流）欸乃渔谣隔一涧
（无所不及）跌宕石中叩一焰
（孰守无心）万化兴衰皆成镜鉴
（动以天行）照霜天
——《万象霜天(Vocaloid全员)》By 伊水 / 流绪 / Creuzer
> Link 万象霜天-Bilibili