回頭補字串（從SAM開始）
# 題面
給定一個長度為 \(n\) 的 01 字串 \(S\)，記以 \(i\) 位置結束的前綴為 \(S[i]\)，
給定 \(m\) 組詢問，每組詢問給出 \(l,r\)，求
\[\max_{i,j}\big\{\operatorname{LCS}(S[i],S[j])\mid i\neq j\land l\le i,j\le r\big\} \]資料規模：\(n,m\le 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}(n\log^2n)\)，
再考慮如何計算答案，當子節點 \(v\) 的資訊合并到父節點 \(u\) 上時，考慮每對 \((i,j)\)：\(i\in E_v\), \(j\in E_u\)；\(p_i,p_j\) 的 LCA 就是點 \(u\)，
顯然每對 \((i,j)\) 的 LCS 可以貢獻到滿足 \(l\le \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\) 時，對于每個 \(i\in E_u\)，我們只需要找到 \(E_v\) 中 \(i\) 的 “前驅” 和 “后繼” \(j\)，因為比前驅更小的 \(j\)，其能夠貢獻到的 \((l,r)\) 的范圍更小，比后繼更大的 \(j\) 同理，
合并次數是 \(\mathcal{O}(n\log n)\)，于是三元組的數量也是 \(\mathcal{O}(n\log 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}(n\log^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\n",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\n",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\n",ans[i]);
return 0;
}
THE END
Thanks for reading!
（天地雖大）水中明月又一片
（其化均也）心上塵埃只一葉
（萬物雖多）提指拈花卻一線
（其治一也）恍然一念間
（四達通流）欸乃漁謠隔一澗
（無所不及）跌宕石中叩一焰
（孰守無心）萬化興衰皆成鏡鑒
（動以天行）照霜天
——《萬象霜天(Vocaloid全員)》By 伊水 / 流緒 / Creuzer
> Link 萬象霜天-Bilibili
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/266264.html
標籤：其他
上一篇：buuctf