CodeForces - 1037H: Security(SAM+线段树合并)

2021年09月15日 阅读数:3
这篇文章主要向大家介绍CodeForces - 1037H: Security(SAM+线段树合并),主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

题意:给定字符串S;  Q次询问,每次询问给出(L,R,T),让你在S[L,R]里面找一个字典序最小的子串,其字典序比T大。 没有则输出-1;c++

思路:比T字典序大,并且要求字典最小,显然就是在T的尾巴加一个很小的字符,若是不存在,则依次删去尾巴,直到“存在”。spa

而“存在”是指,前缀lim+一个字符‘x’后存在于[L+lim,R]中, 因此咱们须要预处理出全部点的endpos,这个用线段树合并就能够了。code

注意这里是每个节点都要记录,因此和普通的启发式合并不太同样,这里须要每次新开一个节点。blog

#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);
return 0; }
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; }