【Luogu3732】[HAOI2017]供给侧改革（Trie树）

时间：2021-03-02 14:21:46

【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;

}

相关文章