cf1037H

Posted on   |   In ,

题意

给定一个串$S$ $q$次查询在S[l,r]中字典序比询问串大的字典序最小的那个

题解

这题有两个版本的写法

SAM

考虑对原串建SAM 用线段树合并维护每个节点上$Right$集合

对于每次查询

从前往后对于每个位置找到恰好比当前前缀字典序大的 并满足区间范围的位置

然后输出即可

复杂度$O(26*nlogn)$

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define link(x) for(edge *j=h[x];j;j=j->next)
#define inc(i,l,r) for(int i=l;i<=r;i++)
#define dec(i,r,l) for(int i=r;i>=l;i--)
const int MAXN=6e5+10;
const double eps=1e-8;
const int mod=1e9+9;
#define ll long long
using namespace std;
struct edge{int t;edge*next;}e[MAXN<<1],*h[MAXN],*o=e;
void add(int x,int y){o->t=y;o->next=h[x];h[x]=o++;}
ll read(){
    ll x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    return x*f;
}


char str[MAXN];
int cnt,rt,cur,tot;
int Rt[MAXN],Len,fa[MAXN],dis[MAXN],ch[MAXN][31];
typedef struct node{
    int l,r,num;
}node;
node d[MAXN*41];
void update(int &x,int l,int r,int t){
    if(!x)x=++tot;
    d[x].num++;
    if(l==r)return ;
    int mid=(l+r)>>1;
    if(t<=mid)update(d[x].l,l,mid,t);
    else update(d[x].r,mid+1,r,t);
}
void built(int x){
    int last=cur;cur=++cnt;dis[cur]=dis[last]+1;int p=last;
    update(Rt[cur],1,Len,dis[cur]);
    for(;p&&!ch[p][x];p=fa[p])ch[p][x]=cur;
    if(!p)fa[cur]=rt;
    else{
	int q=ch[p][x];
	if(dis[q]==dis[p]+1)fa[cur]=q;
	else{
	    int nt=++cnt;dis[nt]=dis[p]+1;
	    memcpy(ch[nt],ch[q],sizeof(ch[q]));
	    fa[nt]=fa[q];fa[q]=fa[cur]=nt;
	    for(;ch[p][x]==q;p=fa[p])ch[p][x]=nt;
	}
    }
}
void merge(int &x,int y,int l,int r){
    if(!y)return ;
    if(!x){x=y;return ;}
    int t=++tot;d[t]=d[x];d[t].num+=d[y].num;x=t;
    if(l==r)return ;
    int mid=(l+r)>>1;
    merge(d[x].l,d[y].l,l,mid);
    merge(d[x].r,d[y].r,mid+1,r);
}
int ans;
void query(int x,int l,int r,int ql,int qr){
    if(ql<=l&&r<=qr){ans+=d[x].num;return ;}
    int mid=(l+r)>>1;
    if(ql<=mid)query(d[x].l,l,mid,ql,qr);
    if(qr>mid)query(d[x].r,mid+1,r,ql,qr);
}
void dfs(int x){
    link(x)dfs(j->t),merge(Rt[x],Rt[j->t],1,Len);
}
char s[MAXN];
bool check(int x,int l,int r){
    if(!x||l>r)return 0;
    ans=0;query(x,1,Len,l,r);
    if(ans>=1)return 1;
    return 0;
}
int main(){
    scanf("%s",str);int len=strlen(str);Len=len;
    rt=cnt=cur=1;
    for(int i=0;i<len;i++)built(str[i]-'`');
    inc(i,1,cnt)add(fa[i],i);
    dfs(rt);
    int q=read();
    while(q--){
	int l=read();int r=read();scanf("%s",s);int temp=rt;
	len=strlen(s);s[len]='`';int len1=0,len2,len3;int Temp,TEMP;
	int pos1=-1;int pos2;
	for(int i=0;i<=len;i++){
	    int t=s[i]-'`';Temp=temp;len2=len1;
	    for(int j=t+1;j<=26;j++){
		if(!ch[Temp][j])continue;
		if(!check(Rt[ch[Temp][j]],l+i,r))continue;
		pos1=i;pos2=j;
		break;
	    }
	    if(!ch[temp][t])break;
	    if(!check(Rt[ch[temp][t]],l+i,r))break;
	    temp=ch[temp][t];
	}
	if(pos1==-1)printf("%d\n",-1);
	else{
	    for(int i=0;i<pos1;i++)printf("%c",s[i]);
	    printf("%c",(char)('a'+pos2-1));
	    printf("\n");
	}
    }
    return 0;
}

SA

离线询问 把原串和询问串用一个字符链接在一起 跑$SA$

然后按着$rank$从大到小枚举 因为对于每个询问 满足条件的必然是$rank$比询问位置大的

我们从两个方向统计答案

对于原串的下标满足$[l,r-min(rmq(rank[last],i),len)]$ 维护$rank$的最小值

然后对于下标满足$[r-len,r]$暴力枚举其$rank$以及其$lcp$是否满足条件 并维护满足条件里面$rank$最小

的下标

复杂度$O(nlogn)$

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define inc(i,l,r) for(int i=l;i<=r;i++)
#define dec(i,r,l) for(int i=r;i>=l;i--)
const int MAXN=6e5+10;
const double eps=1e-8;
const int inf=1e9+9;
#define ll long long
using namespace std;
ll read(){
    ll x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    return x*f;
}

char str[MAXN],s[MAXN];
int vis[MAXN];
typedef struct node{
    int l,r;
}node;
node que[MAXN];
int txt[MAXN],sa[MAXN],td[MAXN],rank1[MAXN],rank2[MAXN],t1[MAXN],t2[MAXN];
int ma[MAXN];
int dp[MAXN][21];
bool cmp(int f[],int t,int w,int k){return f[t]==f[w]&&f[t+k]==f[w+k];}
void Sa(){
    int len=strlen(str);int m=256;
    int *t1=rank1;int *t2=td;
    for(int i=0;i<m;i++)txt[i]=0;
    for(int i=0;i<len;i++)txt[str[i]]++,rank1[i]=str[i];
    for(int i=1;i<m;i++)txt[i]+=txt[i-1];
    for(int i=len-1;i>=0;i--)sa[--txt[str[i]]]=i;
    for(int k=1;k<=len;k<<=1){
	int p=0;
	for(int i=len-k;i<len;i++)td[p++]=i;
	for(int i=0;i<len;i++)if(sa[i]>=k)td[p++]=sa[i]-k;
	for(int i=0;i<m;i++)txt[i]=0;
	for(int i=0;i<len;i++)txt[rank1[i]]++;
	for(int i=1;i<m;i++)txt[i]+=txt[i-1];
	for(int i=len-1;i>=0;i--)sa[--txt[rank1[td[i]]]]=td[i];
	swap(rank1,td);rank1[sa[0]]=0;
	p=1;
	for(int i=1;i<len;i++)rank1[sa[i]]=cmp(td,sa[i],sa[i-1],k)?p-1:p++;
	if(p>=len)break;
	m=p;
    }
    for(int i=0;i<len;i++)rank2[sa[i]]=i;
}
int h[MAXN],H[MAXN],Len;
void hh(){
    int len=strlen(str);
    for(int i=0;i<len;i++){
	if(rank2[i]==0)continue;
	int t=sa[rank2[i]-1];int w=i;int k=0;
	if(i==0||H[i-1]<=1)k=0;else k=H[i-1]-1,t+=k,w+=k;
	while(t<len&&w<len){
	    if(str[t]==str[w])k++;else break;
	    t++;w++;
	}
	H[i]=k;h[rank2[i]]=k;
    }
}
void St(){
    int len=strlen(str);
    inc(i,2,len)ma[i]=ma[i/2]+1;
    for(int i=1;i<len;i++)dp[i][0]=h[i];
    for(int j=1;j<=20;j++){
	for(int i=1;i+(1<<j)<=len;i++){
	    dp[i][j]=min(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
	}
    }
}
int rmq(int l,int r){
    l++;
    int k=ma[r-l+1];
    return min(dp[l][k],dp[r-(1<<k)+1][k]);
}
int minn[MAXN<<2],LEN[MAXN];
void built(int x,int l,int r){
    minn[x]=inf;
    if(l==r)return ;
    int mid=(l+r)>>1;
    built(x<<1,l,mid);
    built(x<<1|1,mid+1,r);
}
void update(int x,int l,int r,int t,int k){
    minn[x]=min(minn[x],k);
    if(l==r)return ;
    int mid=(l+r)>>1;
    if(t<=mid)update(x<<1,l,mid,t,k);
    else update(x<<1|1,mid+1,r,t,k);
}
int ans1;
void query(int x,int l,int r,int ql,int qr){
    if(ql<=l&&r<=qr){ans1=min(ans1,minn[x]);return ;}
    int mid=(l+r)>>1;
    if(ql<=mid)query(x<<1,l,mid,ql,qr);
    if(qr>mid)query(x<<1|1,mid+1,r,ql,qr);
}
pii ans[MAXN];
void solve(){
    int len=strlen(str);int last=0;
    for(int i=len-1;i>=1;i--){
	//cout<<i<<":::: "<<endl;
	if(!vis[sa[i]]&&sa[i]<Len){
	    last=i;
	    update(1,1,Len,sa[i]+1,i);
	    continue;
	}
	if(!vis[sa[i]])continue;
	int k=vis[sa[i]];
	int l=que[k].l;int r=que[k].r;
	if(last)r-=min(rmq(i,last),LEN[k]);
	//cout<<l<<" "<<r<<endl;
	ans1=inf;
	if(l<=r)query(1,1,Len,l,r);
	for(int j=max(que[k].r-LEN[k],que[k].l-1);j<que[k].r;j++){
	    if(rank2[j]<=i)continue;
	    int k1=min(rmq(i,rank2[j]),LEN[k]);
	    if(j+k1+1>que[k].r)continue;
	    if(ans1>rank2[j])ans1=rank2[j];
	}
	if(ans1==inf)ans[k].first=-1;
	else ans[k].first=ans1,ans[k].second=rmq(i,ans1);
    }
}
int main(){
    scanf("%s",str);int len=strlen(str);Len=len;str[len]='$';len++;
    built(1,1,Len);
    int n=read();
    inc(i,1,n){
	que[i].l=read();que[i].r=read();
	scanf("%s",s);int len1=strlen(s);LEN[i]=len1;
	for(int j=0;j<len1;j++){
	    if(j==0)vis[len]=i;
	    str[len++]=s[j];
	}
	str[len++]='$';
    }
    str[len]='\0';
    Sa();hh();St();
    //cout<<str<<endl;
    //inc(i,1,len-1)cout<<sa[i]<<" ";
    //cout<<endl;
    solve();
    inc(i,1,n){
	if(ans[i].first==-1)printf("%d\n",-1);
	else{
	    for(int j=sa[ans[i].first];j<=sa[ans[i].first]+ans[i].second;j++)printf("%c",str[j]);
	    printf("\n");
	}
    }
    return 0;
}