bzoj5405 platform

bzoj5405 platform

原题传送门:>Here<

我们考虑对原串反向建后缀自动机。这样后缀自动机上的每一个点表示的就是原串上的一堆前缀。

我们发现一个性质:这些前缀的排名必定是连续的。

我们考虑证明。

假设有一个节点表示前缀

1
2
3
ABB
AB
A

如果它的排名不连续,则必定有一个子串是这些前缀加上一些字符,如$ABC$。

假设存在$ABC$,则$AB$与$ABB$的end_pos必定不同,所以$AB$和$B$在建自动机时(建机?)会被克隆出来,成为一个新点。所以不可能出现这种情况。

接下来,我们发现可以通过$dfs$得到每个节点的$rank$。我们只要按照字典序顺序后序遍历整棵树就行了。

在查询时,我们枚举原串的每个后缀。

当枚举到$i$时,我们发现$rank(i,j)$必定是单调下降的,而$\sum_{k=i}^{j}a_k$是单调不降的。所以至多有一个点使得两者相等。我们只要二分这个位置即可。

对于每个位置,我们通过倍增找到$s[i\cdots j]$被机上的哪个节点表示,然后该子串的$rank$就是$rank_p+len_p-(j-i+1)$。

注意开$long \space long$。

代码:

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
#include <cstdio>
#include <cstring>
#include <algorithm>
#define int long long

int son[500001][26],size[500001],len[500001],last=1,cnt=1,fa[500001],n,end[500001],rank[500001],now=1;
long long a[300001];
int head[500001],nxt[500001],b[500001],k,pre[500001][21],p,length;
void push(int s,int t){
nxt[++k]=head[s];
head[s]=k;
b[k]=t;
}
char str[200001];
void add(int x,int ep){
int p=last;
len[last=++cnt]=len[p]+1;
size[last]=1;
end[last]=ep;
for(;p&&!son[p][x];p=fa[p])son[p][x]=last;
if(!p){fa[last]=1;return;}
int q=son[p][x];
if(len[q]==len[p]+1){fa[last]=q;return;}
len[++cnt]=len[p]+1;
end[cnt]=ep;
for(int i=0;i<26;i++)son[cnt][i]=son[q][i];
fa[cnt]=fa[q],fa[q]=fa[last]=cnt;
for(;p&&son[p][x]==q;p=fa[p])son[p][x]=cnt;
}
struct point{
int ord,v;
bool operator<(const point &a) const{
return v<a.v;
}
}tem[400001];
int top;
void dfs(int x){
int start=top;
for(int i=head[x];i;i=nxt[i])tem[++top]=(point){b[i],str[n-(end[b[i]]-len[x])+1]};
std::sort(tem+start+1,tem+top+1);
// printf("dfs %d\n",x);
// for(int i=start+1;i<=top;i++)printf("(%d %c)",tem[i].ord,tem[i].v);
// putchar('\n');
while(top!=start){
dfs(tem[top].ord);
size[x]+=size[tem[top].ord];
--top;
}
rank[x]=now;
now+=(len[x]-len[fa[x]]);
}
struct answer{
int l,r;
bool operator<(const answer &a) const {
return l==a.l?r<a.r:l<a.l;
}
}fin[200001];
int T;
int getrk(int x,int start){
int ans=p;
for(int i=20;~i;i--)
if((start+len[pre[ans][i]]-1)>=x&&pre[ans][i]!=1)ans=pre[ans][i];
return rank[ans]+start+len[ans]-1-x;
}
void check(int l,int r){
int left=l;
// printf("check %d %d %d %d\n",l,r,rk,start);
int mid,ans=-1;
while(l<=r){
mid=(l+r)>>1;
if(a[mid]-a[left-1]>=getrk(mid,left))ans=mid,r=mid-1;
else l=mid+1;
}
if(a[ans]-a[left-1]==getrk(ans,left))fin[++T]=(answer){left,ans};
}
signed main(){
// freopen("in.txt","r",stdin);
// freopen("out2.txt","w",stdout);
scanf("%s",str+1);
n=strlen(str+1);
// if(n>50)return 0;
for(int i=n;i;i--)add(str[i]-'a',n-i+1);
for(int i=2;i<=cnt;i++)push(fa[i],i);

dfs(1);
// for(int i=1;i<=cnt;i++){
// printf("%d : -> %d : ",i,fa[i]);
// for(int j=0;j<26;j++)
// if(son[i][j])printf("(%c %d)",j+'a',son[i][j]);
// printf("%d\n",rank[i]);
// }

for(int i=1;i<=n;i++)scanf("%lld",a+i),a[i]+=a[i-1];

for(int i=1;i<=cnt;i++)pre[i][0]=fa[i];

for(int i=1;i<=20;i++)
for(int j=1;j<=cnt;j++)
pre[j][i]=pre[pre[j][i-1]][i-1];

p=1,length=0;
for(int i=n;i;i--){
while(p&&!son[p][str[i]-'a'])p=fa[p];
if(!p)p=1,length=0;
else{
length=std::min(length,len[p])+1;
p=son[p][str[i]-'a'];
}
// printf("%d %d\n",p,length);
check(i,i+length-1);
}
std::sort(fin+1,fin+T+1);
printf("%lld\n",T);
for(int i=1;i<=T;i++)printf("%lld %lld\n",fin[i].l,fin[i].r);
}

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×