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

2019/03/24 23:07
阅读数 7

【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;
}
展开阅读全文
lcp
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部