题意：给定字符串S； Q次询问，每次询问给出(L,R,T)，让你在S[L,R]里面找一个字典序最小的子串，其字典序比T大。 没有则输出-1；
思路：比T字典序大，而且要求字典最小，显然就是在T的尾巴加一个很小的字符，如果不存在，则依次删去尾巴，直到“存在”。
而“存在”是指，前缀lim+一个字符‘x’后存在于[L+lim,R]中， 所以我们需要预处理出所有点的endpos，这个用线段树合并就可以了。
注意这里是每一个节点都要记录，所以和普通的启发式合并不太一样，这里需要每次新开一个节点。
#include<bits/stdc++.h> #define rep2(i,a,b) for(int i=a;i>=b;i--) #define rep(i,a,b) for(int i=a;i<=b;i++) using namespace std; const int maxn=400010; char c[maxn]; int rt[maxn],N,tot; struct in{ int L,R,sum; }s[maxn*22]; void ins(int &now,int L,int R,int p) { if(!now) now=++tot; s[now].sum++; if(L==R) return ; int Mid=(L+R)>>1; if(p<=Mid) ins(s[now].L,L,Mid,p); else ins(s[now].R,Mid+1,R,p); } int merge(int x,int y) { if(!x||!y) return x|y; int now=++tot; s[now].L=merge(s[x].L,s[y].L); s[now].R=merge(s[x].R,s[y].R); s[now].sum=s[s[now].L].sum+s[s[now].R].sum; return now; } bool query(int Now,int L,int R,int l,int r) { if(!Now||l>r) return false; if(l<=L&&r>=R) return s[Now].sum; int Mid=(L+R)>>1; if(l<=Mid&&query(s[Now].L,L,Mid,l,r)) return true; if(r>Mid) return query(s[Now].R,Mid+1,R,l,r); } struct SAM{ int ch[maxn][26],fa[maxn],maxlen[maxn],cnt,last; int a[maxn],b[maxn]; void init() { cnt=last=1; memset(ch[1],0,sizeof(ch[1])); } int add(int x,int id) { int np=++cnt,p=last; last=np; ins(rt[np],1,N,id); maxlen[np]=maxlen[p]+1; memset(ch[np],0,sizeof(ch[np])); while(p&&!ch[p][x]) ch[p][x]=np,p=fa[p]; if(!p) fa[np]=1; else { int q=ch[p][x]; if(maxlen[q]==maxlen[p]+1) fa[np]=q; else { int nq=++cnt; maxlen[nq]=maxlen[p]+1; fa[nq]=fa[q]; fa[q]=fa[np]=nq; memcpy(ch[nq],ch[q],sizeof(ch[q])); while(p&&ch[p][x]==q) ch[p][x]=nq,p=fa[p]; } } } void sort() { rep(i,1,cnt) a[i]=0; rep(i,1,cnt) a[maxlen[i]]++; rep(i,1,cnt) a[i]+=a[i-1]; rep(i,1,cnt) b[a[maxlen[i]]--]=i; for(int i=cnt;i>=1;i--) { int x=b[i]; if(fa[x]) rt[fa[x]]=merge(rt[fa[x]],rt[x]); } } }T; int pos[maxn],Q; void solve() { int L,R,len,fcy; scanf("%d%d%s",&L,&R,c+1); len=strlen(c+1); int now=1,lim=len; c[len+1]=‘a‘-1; rep(i,1,len) { if(T.ch[now][c[i]-‘a‘]) now=T.ch[now][c[i]-‘a‘]; else { lim=i-1; break;} pos[i]=now; } fcy=-1; pos[0]=1; for(int i=lim;i>=0&&fcy==-1;i--){ for(int j=c[i+1]-‘a‘+1;j<26;j++){ int v=T.ch[pos[i]][j]; if(!v) continue; if(query(rt[v],1,N,L+i,R)) { fcy=i+1; c[fcy]=‘a‘+j; break; } } } if(fcy==-1) puts("-1"); else { rep(i,1,fcy) putchar(c[i]); puts(""); } } int main() { T.init(); scanf("%s",c+1); N=strlen(c+1); rep(i,1,N) T.add(c[i]-‘a‘,i); T.sort(); scanf("%d",&Q); while(Q--) solve(); return 0; }
CodeForces - 1037H: Security（SAM+线段树合并）
原文：https://www.cnblogs.com/hua-dong/p/11433537.html