CF1037H Security
FxorG
2021-07-09 08:31:15
## $\text{Solution}$
首先对于字典序最小，我们可以来个贪心：
假如是 $aab$ ，那么我们先考虑能不能在 $[L,R]$ 内匹配到 $aab$ ，再考虑能否再添上一个最小的字母。假如不行，返回上一步，找一个大于 $b$ 的最小字母，凑出来就字典序最大了。不行的话就再回跳。
总结下：
1. 假如前面全部一模一样匹配成功，且全部匹配完，只需要看能否添上一个最小的即可。
2. 看能否当前位匹配一样的。
3. 能否匹配更大的，直接退出。
注意下，它们是有优先级的。
那么，对于一个字符串，我们怎么考虑它是否在 $[L,R]$ 出现？
考虑当前匹配到 SAM 的 $p$ 节点，然后 SAM 的父亲是儿子的后缀，说明父亲这个状态在儿子中都有出现过，那么我们只需要判断下这个子树里有没有在 $[L,R]$ 之中的即可。
这里我线段树合并不熟，写了个主席树+dfs序。
## $\text{Code}$
```cpp
#include <bits/stdc++.h>
#define N (int)(3e5+5)
using namespace std;
struct edge {
int nex,to;
}e[N];
char s[N];
int head[N],cnt,sz[N],val[N],fa[N],len[N],son[26][N],id[N],rk[N],rt[N],id_tot;
int n,m,M,las=1,tot=1;
void add_edge(int x,int y) {
e[++cnt].nex=head[x]; e[cnt].to=y;
head[x]=cnt;
}
void ins(int c,int v) {
int pre=las,x=++tot; las=x; len[x]=len[pre]+1; val[x]=v;
for(;pre&&!son[c][pre];pre=fa[pre]) son[c][pre]=x;
int y=son[c][pre];
if(!pre) fa[x]=1;
else if(len[pre]+1==len[y]) fa[x]=y;
else {
int p=++tot; len[p]=len[pre]+1;
fa[p]=fa[y]; fa[x]=fa[y]=p;
for(int i=0;i<26;i++) son[i][p]=son[i][y];
for(;pre&&son[c][pre]==y;pre=fa[pre]) son[c][pre]=p;
}
//return x;
}
int dtot=0;
void dfs(int x) {
id[x]=++dtot; rk[dtot]=x; sz[x]=1;
for(int i=head[x];i;i=e[i].nex) {
int y=e[i].to;
dfs(y); sz[x]+=sz[y];
}
}
int ls[N*30],rs[N*30],sum[N*30],pos_tot=0;
void update(int &cur,int pre,int l,int r,int x) {
if(!cur) cur=++pos_tot;
sum[cur]=sum[pre]+1;
if(l==r) return ;
int mid=(l+r)>>1;
if(x<=mid) rs[cur]=rs[pre],update(ls[cur],ls[pre],l,mid,x);
else ls[cur]=ls[pre],update(rs[cur],rs[pre],mid+1,r,x);
}
int query(int pre,int cur,int l,int r,int x) {
if(l==r&&l==x) return sum[cur]-sum[pre];
if(l==r) return 0;
int mid=(l+r)>>1;
if(x<=mid) return query(ls[pre],ls[cur],l,mid,x);
else return sum[ls[cur]]-sum[ls[pre]]+query(rs[pre],rs[cur],mid+1,r,x);
}
char ans[N];
int ans_tot=0;
bool check(int x,int L,int R) {
int l=id[x],r=id[x]+sz[x]-1;
// cout<<(char)(x+'a')<<' '<<L<<" "<<R<<" "<<query(rt[l-1],rt[r],1,n,R)-query(rt[l-1],rt[r],1,n,L-1)<<'\n';
return query(rt[l-1],rt[r],1,M,R)-query(rt[l-1],rt[r],1,M,L-1)>0;
}
bool solve(int p,int x,int l,int r) {
if(x==n+1) {
for(int i=0;i<26;i++) {
if(son[i][p]&&check(son[i][p],l,r)) {
ans_tot=x; ans[ans_tot]=i; return 1;
}
}
return 0;
}
bool fl=0;
if(son[s[x]-'a'][p]) {
int t=son[s[x]-'a'][p];
if(check(t,l,r)) fl=solve(t,x+1,l+1,r);
if(fl) ans[x]=s[x]-'a';
}
if(fl) return 1;
for(int i=s[x]-'a'+1;i<26;i++) {
if(son[i][p]&&check(son[i][p],l,r)) {
ans_tot=x; ans[x]=i; return 1;
}
}
return 0;
}
int main() {
scanf("%s%d",s+1,&m); M=n=strlen(s+1);
for(int i=1;i<=n;i++) ins(s[i]-'a',i);
for(int i=2;i<=tot;i++) add_edge(fa[i],i);
dfs(1); //build(1,1,tot);
for(int i=1;i<=tot;i++) {
if(val[rk[i]]) update(rt[i],rt[i-1],1,n,val[rk[i]]);
else rt[i]=rt[i-1];
}
for(int i=1;i<=m;i++) {
int L,R;
scanf("%d%d%s",&L,&R,s+1); n=strlen(s+1); ans_tot=0;
if(solve(1,1,L,R)) {
for(int i=1;i<=ans_tot;i++) printf("%c",ans[i]+'a');
puts("");
} else puts("-1");
}
return 0;
}
```