【Luogu3732】[HAOI2017]供给侧改革(Trie树)

【Luogu3732】[HAOI2017]供给侧改革(Trie树)

题面

洛谷

给定一个纯随机的\(01\)串,每次询问\([L,R]\)之间所有后缀两两之间的\(LCP\)的最大值。

题解

一个暴力的想法是构建\(SA\)之后把所有位置按照\(rank\)排序,每次询问相邻的两个\(LCP\)就行了,然后拿\(set\)维护插入的操作。

然而并没有用到串随机的性质。

既然是随机的,那么大力猜一猜他们的\(lcp\)的长度不会很长,大概估计一个\(40\)左右吧。

把询问离线挂在右端点上,从左往右把每个后缀的前\(40\)个位置插入\(trie\)数,记录可以取到\(LCP\)为每个值的时候的最靠右的端点,然后统计一下就好了。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
#define MAX 100100
#define mp make_pair
inline int read()
{
int x=0;bool t=false;char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=true,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return t?-x:x;
}
int n,Q,p[MAX],ans[MAX];char ch[MAX];
int L[MAX],R[MAX];
vector<int> A[MAX];
int fr[MAX];
struct Node{int ch[2],lst;}t[MAX*50];
int tot=1;
void Insert(int p)
{
int nw=1;fr[0]=p;
for(int i=p;i<=n&&i<=p+40;++i)
{
int c=ch[i]-48;
if(!t[nw].ch[c])t[nw].ch[c]=++tot;
nw=t[nw].ch[c];
fr[i-p+1]=max(fr[i-p+1],t[nw].lst);
t[nw].lst=p;
}
}
int main()
{
n=read();Q=read();scanf("%s",ch+1);
for(int i=1;i<=Q;++i)L[i]=read(),R[i]=read(),A[R[i]].push_back(i);
for(int i=1;i<=n;++i)
{
Insert(i);
for(int q:A[i])
{
int sum=0;
for(int j=1;j<=40;++j)
if(fr[j]>=L[q])sum+=fr[j]-L[q]+1;
ans[q]=sum;
}
}
for(int i=1;i<=Q;++i)printf("%d\n",ans[i]);
return 0;
}
上一篇:宝塔面板部署springboot项目,ssh配置(linux)


下一篇:DevExpress XtraReport报表预览时可编辑的功能