【HEOI2016】字符串

Source

HEOI2016
loj2868

Hint

请先思考后再展开

二分答案

Solution

请先思考后再展开

二分答案,height+主席树,化化柿子发现很好check,时间复杂度为 $O(nlog^2n)$

还有一个sam的做法,先翻转变为求后缀,然后网上的线段树合并需要新建节点,这里给出一个和普通线段树合并没区别的做法(主要是我比较菜,以为线段树合并必须在线):在外层枚举这是第几次二分,然后把目前依然没有得出答案的人倍增挂到parent树上,然后线段树合并求right集合,时间复杂度为 $O(n log^2 n)$

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
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
//Zory-2019
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
#include<deque>
using namespace std;
namespace mine
{
typedef long long ll;
const int INF=0x3f3f3f3f;
const ll LINF=0x3f3f3f3f3f3f3f3fLL;
ll qread()
{
ll ans=0;char c=getchar();int f=1;
while(c<'0' or c>'9') {if(c=='-') f=-1;c=getchar();}
while('0'<=c and c<='9') ans=ans*10+c-'0',c=getchar();
return ans*f;
}
void write(ll num)
{
if(num<0) {num=-num;putchar('-');}
if(num>9) write(num/10);
putchar('0'+num%10);
}
void writeln(ll num){write(num);puts("");}
inline void chmax(int &x,int y) {x=x>y?x:y;}
inline void chmin(int &x,int y) {x=x<y?x:y;}
inline void chmaxll(ll &x,ll y) {x=x>y?x:y;}
inline void chminll(ll &x,ll y) {x=x<y?x:y;}
#define PB push_back
#define FR first
#define SE second
#define MP make_pair
#define pr pair<ll,ll>
const int MAX_N=110000;
struct CMT
{
struct Nod{int c,lc,rc;}p[MAX_N*30];
int id;CMT(){id=0;memset(p,0,sizeof p);}
void add(int &x,int l,int r,int pos)
{
if(x==0) x=++id;
p[x].c++;
if(l==r) return;
int mid=(l+r)>>1;
if(pos<=mid) add(p[x].lc,l,mid,pos);
else add(p[x].rc,mid+1,r,pos);
}
void merg(int x,int &y,int l,int r)
{
if(x==0) return;
if(y==0) {y=x;return;}
p[y].c+=p[x].c;
if(l==r) return;
int mid=(l+r)>>1;
merg(p[x].lc,p[y].lc,l,mid);
merg(p[x].rc,p[y].rc,mid+1,r);
}
int ask(int x,int y,int l,int r,int tt)
{
if(tt<l or tt>r or y==0) return 0;
if(l==r) return p[y].c-p[x].c;
int mid=(l+r)>>1;
if(tt>mid) return (p[p[y].lc].c-p[p[x].lc].c)+ask(p[x].rc,p[y].rc,mid+1,r,tt);
return ask(p[x].lc,p[y].lc,l,mid,tt);
}
}cmt;
int rt[MAX_N];
int n;
struct STB
{
int mm[MAX_N][20],bin[30],lg[MAX_N];
void pre()
{
bin[0]=1;for(int i=1;i<30;i++) bin[i]=bin[i-1]<<1;
lg[1]=0;for(int i=2;i<MAX_N;i++) lg[i]=lg[i>>1]+1;
for(int i=1;i<20;i++) for(int j=2;j<=n-bin[i]+1;j++) mm[j][i]=min(mm[j][i-1],mm[j+bin[i-1]][i-1]);
}
int ask(int l,int r)
{
int t=lg[r-l+1];
return min(mm[l][t],mm[r-bin[t]+1][t]);
}
}stb;
char s[MAX_N];
struct SA
{
int sa[MAX_N],rk[MAX_N],wr[MAX_N*2],tmp[MAX_N],ct[MAX_N];
void getsa()
{
memset(ct,0,sizeof ct);
for(int i=1;i<=n;i++) ct[rk[i]=s[i]]++;
for(int i=1;i<MAX_N;i++) ct[i]+=ct[i-1];
for(int i=n;i>=1;i--) sa[ct[rk[i]]--]=i;
int ln=1;
while(ln<n)
{
int tot=0;for(int i=1;i<=n;i++) if(sa[i]+ln>n) tmp[++tot]=sa[i];
for(int i=1;i<=n;i++) if(sa[i]-ln>=1) tmp[++tot]=sa[i]-ln;
memset(ct,0,sizeof ct);memcpy(wr,rk,sizeof rk);
for(int i=1;i<=n;i++) ct[ wr[tmp[i]] ]++;
for(int i=1;i<MAX_N;i++) ct[i]+=ct[i-1];
for(int i=n;i>=1;i--) sa[ct[ wr[tmp[i]] ]--]=tmp[i];
int tt=1;rk[sa[1]]=1;
for(int i=2;i<=n;i++)
{
if(wr[sa[i-1]+ln]!=wr[sa[i]+ln] or wr[sa[i-1]]!=wr[sa[i]]) tt++;
rk[sa[i]]=tt;
}
ln*=2;
}
}
int hei[MAX_N];
void gethei()
{
int lst=0;
for(int i=1;i<=n;i++)
{
if(rk[i]==1) {hei[1]=0;continue;}
int j=sa[rk[i]-1];if(lst) lst--;
while(max(i,j)+lst<=n and s[i+lst]==s[j+lst]) lst++;
hei[rk[i]]=lst;
}
}
}sa;
bool check(int i,int a,int b,int L)
{
if(i>1)
{
int tl=1,tr=i-1,mx=-1;
while(tl<=tr)
{
int mid=(tl+tr)/2;
if(stb.ask(mid+1,i)>=L) mx=mid,tr=mid-1;
else tl=mid+1;
}
if(mx>0 and cmt.ask(rt[mx-1],rt[i-1],1,n,b-L+1)-cmt.ask(rt[mx-1],rt[i-1],1,n,a-1)>0) return 1;
}
if(i<n)
{
int tl=i+1,tr=n,mi=n+1;
while(tl<=tr)
{
int mid=(tl+tr)/2;
if(stb.ask(i+1,mid)>=L) mi=mid,tl=mid+1;
else tr=mid-1;
}
if(mi<=n and cmt.ask(rt[i],rt[mi],1,n,b-L+1)-cmt.ask(rt[i],rt[mi],1,n,a-1)>0) return 1;
}
return 0;
}
void main()
{
int q;scanf("%d%d%s",&n,&q,s+1);
sa.getsa();sa.gethei();
for(int i=2;i<=n;i++) stb.mm[i][0]=sa.hei[i];
stb.pre();
for(int i=1;i<=n;i++) cmt.add(rt[i],1,n,sa.sa[i]),cmt.merg(rt[i-1],rt[i],1,n);
for(int i=1;i<=q;i++)
{
int a,b,c,d;scanf("%d%d%d%d",&a,&b,&c,&d);
int l=1,r=d-c+1,gg=0;
while(l<=r)
{
int mid=(l+r)/2;
if(check(sa.rk[c],a,b,mid)) gg=mid,l=mid+1;
else r=mid-1;
}
int ans=gg;if(a<=c and c<=b) chmax(ans,min(d-c+1,b-c+1));
printf("%d\n",ans);
}
}
};
int main()
{
srand(time(0));
mine::main();
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/c709.html
转载请注明出处,谢谢!