正題

題目鏈接:https://www.luogu.com.cn/problem/U142356?contestId=37784

---

題目大意

一個字符串，詢問給出$(x,l,r)$表示詢問在$[l,r]$中作為起點找一個后綴它與$x$作為起點的后綴的$LCP$最長，且滿足最長的情況下字典序最小。

---

解題思路

顯然是要再$x$后綴數組的位置上找到一個最前的在$[l,r]$中的數使得$LCP$最長。

我們要先在$SA$上找到$x$在$[l,r]$中的前驅后繼，這個可以用主席樹維護，然后如果是后繼的$LCP$最大那么前驅直接就是答案，否則我們需要二分出一個最前的位置使得這個位置與$x$的$LCP$也是最大的，之后再找這個位置的后繼。

用主席樹維護前驅后繼的問題，我們在第$i$棵樹中插入$r{k}_i$，然后詢問$(x,l,r)$時我們查詢$l～r$樹中在$[1,x?1]$這個范圍有多少個數，若有$k$個，那么詢問$l～r$數中第$k$個數就是前驅，后繼同理。

時間復雜度$O(n\log n)$（二分+RMQ,主席樹的時間復雜度是分開的）

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #include<vector> using namespace std; const int N=2e5+10; struct ask_node{int l,r,id; }; int n,m,rt[N],prt[N],mrk[N]; int lim,sa[N],rk[N],c[N],x[N],y[N]; int lg[N],f[N][20]; vector<ask_node> v[N]; char s[N]; void Qsort(){for(int i=1;i<=lim;i++)c[i]=0;for(int i=1;i<=n;i++)c[x[i]]++;for(int i=1;i<=lim;i++)c[i]+=c[i-1];for(int i=n;i>=1;i--)sa[c[x[y[i]]]--]=y[i],y[i]=0;return; } void Get_SA(){lim=26;for(int i=1;i<=n;i++)x[i]=s[i]-'a'+1,y[i]=i;Qsort();for(int w=1;w<=n;w<<=1){int p=0;for(int i=n-w+1;i<=n;i++)y[++p]=i;for(int i=1;i<=n;i++)if(sa[i]>w)y[++p]=sa[i]-w;Qsort();swap(x,y);p=x[sa[1]]=1;for(int i=2;i<=n;i++)x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+w]==y[sa[i-1]+w])?p:++p;if(p==n)break;lim=p; }return; } void Get_Height(){int k=0;for(int i=1;i<=n;i++)rk[sa[i]]=i;for(int i=1;i<=n;i++){if(rk[i]==1)continue;if(k)k--;int j=sa[rk[i]-1];while(i+k<=n&&j+k<=n&&s[i+k]==s[j+k])k++;f[rk[i]][0]=k;}return; } void Get_ST(){for(int i=2;i<=n;i++)lg[i]=lg[i/2]+1;for(int j=1;j<19;j++)for(int i=1;i+(1<<j-1)<=n;i++)f[i][j]=min(f[i][j-1],f[i+(1<<j-1)][j-1]);return; } int LCP(int l,int r){if(!l||!r)return -1;if(l==r) return n-sa[l]+1;if(l>r) swap(l,r);l++;int z=lg[r-l+1];return min(f[l][z],f[r+1-(1<<z)][z]); } struct Seg_Tree{int cnt,w[N<<5],ls[N<<5],rs[N<<5];int Change(int x,int L,int R,int pos){int now=++cnt;w[now]=w[x]+1;if(L==R)return now;int mid=(L+R)>>1;if(pos<=mid)ls[now]=Change(ls[x],L,mid,pos),rs[now]=rs[x];else ls[now]=ls[x],rs[now]=Change(rs[x],mid+1,R,pos);return now;}int Ask(int x,int y,int L,int R,int l,int r){if(!(w[y]-w[x]))return 0;if(L==l&&R==r)return w[y]-w[x];int mid=(L+R)>>1;if(r<=mid)return Ask(ls[x],ls[y],L,mid,l,r);if(l>mid)return Ask(rs[x],rs[y],mid+1,R,l,r);return Ask(ls[x],ls[y],L,mid,l,mid)+Ask(rs[x],rs[y],mid+1,R,mid+1,r);}int Query(int x,int y,int L,int R,int k){if(L==R)return L;int mid=(L+R)>>1,val=w[ls[y]]-w[ls[x]];if(k<=val)return Query(ls[x],ls[y],L,mid,k);return Query(rs[x],rs[y],mid+1,R,k-val);} }T; int main() { // printf("%d",sizeof(T)/1024/1024);scanf("%s",s+1);n=strlen(s+1);scanf("%d",&m);for(int i=1;i<=m;i++){int x,l,r;scanf("%d%d%d",&x,&l,&r);v[x].push_back((ask_node){l,r,i});}Get_SA();Get_Height();Get_ST();for(int i=1;i<=n;i++)rt[i]=T.Change(rt[i-1],1,n,rk[i]);for(int i=1;i<=n;i++){int x=rk[i];for(int j=0;j<v[i].size();j++){int ans=0;int l=v[i][j].l,r=v[i][j].r,L,R;int sum=T.Ask(rt[l-1],rt[r],1,n,1,x-1);(sum<(T.w[rt[r]]-T.w[rt[l-1]]))?R=T.Query(rt[l-1],rt[r],1,n,sum+1):R=0;(sum)?L=T.Query(rt[l-1],rt[r],1,n,sum):L=0;ans=LCP(x,R);sum=LCP(L,x);if(ans>sum){prt[v[i][j].id]=ans;mrk[v[i][j].id]=sa[R];continue;}L=1;R=x;while(L<=R){int mid=(L+R)>>1;if(LCP(mid,x)<sum)L=mid+1;else R=mid-1;}R=T.Ask(rt[l-1],rt[r],1,n,1,L-1);prt[v[i][j].id]=sum;mrk[v[i][j].id]=sa[T.Query(rt[l-1],rt[r],1,n,R+1)];}}for(int i=1;i<=m;i++)printf("%d %d\n",prt[i],mrk[i]); }

總結

以上是生活随笔為你收集整理的[2020.11.26NOIP模拟赛]勇者的后缀【SA,RMQ,主席树,二分】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。