HAOI 2017 供给侧改革（trie）

发表于 |
字数统计: 962字 | 阅读时长 ≈ 4min

【HAOI2017】供给侧改革

问题描述

Anihc国提高社会生产力水平.落实好以人民为中心的发展思想。决定进行供给侧结构性改革。

为了提高供给品质.你调查了某个产业近来 $ n $ 个时期的供求关系平衡情况.每个时期的情况都用 $ 0 $ 或 $ 1 $ 中的一个数字来表示.于是这就是—个长度为 $ n $ 的 $ 01 $ 字符串 $S$ 。为了更好的了解这一些数据.你需要解决一些询问.我们令 $ data(l,r) $ 表示：在字符串 $S$ 中.起始位置在$ [l,r] $之间的这些后缀之中，具有最长公共前缀的两个后缀的最长公共前缀的长度。

对于每一个询问 $ L $ , $ R $ .求

$ ans = \sum\limits_{ L \le i \lt R } data(i, R) $

由于你其实根本没有时间调查，所以这些数据都是乱编的，即串S中的每一位都是在 $ 0 $ 和 $ 1 $ 之间随机产生的。

输入格式

第一行 $ 2 $ 个整数 $ n $ , $ Q $，表示字符串的长度，以及询问个数

接下来一行长度为 $n$ 的一个 $01$ 串 $S$

接下来 $Q$ 行，每行 $2$ 个整数 $L,R$ .一个询问 $L.R$

输出格式

共 $Q$ 行.每行一个整数.表示对应询问的答案。

样例输入

6 3

010110

2 5

1 6

1 2

样例输出

4

6

0

提示

对于所有的数据保证：$ n <= 100000 $ , $ Q<= 100000 $ , $ 1<=L<R<=n $ , $01$ 串随机生成。

这题有一个强限制，$01$串随机生成。因此我们大胆猜测$LCP$的长度不会太大，估测个40差不多了。

那么可以怎么做的，我们考虑对询问按右端点排序，那么从左往右处理询问，每次将以当前右端点前的位置为开头的后缀加到trie里面去，只用加每个后缀的前40位，然后记录一个数组$Max[i]$表示长度为$i$的$LCP$的最后出现位置时一个长度为$i$的后缀倒数第二次出现的位置，这个可以在$trie$上记录每个串上次出现的位置，然后再访问到的时候就可以用上次的位置来更新$Max$

然后对每个询问，枚举$Max[i]$，如果$Max[i]>=l$，那么就存在长度为$i$的$LCP$在范围内。

复杂度$O(q\log q+40n)$

代码：

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
#include<stdio.h>
#include<algorithm>
#define N 100005
#define M 4000005
using namespace std;
char buf[1<<20],*p1,*p2;
#define GC (p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?0:*p1++)
inline int _R()
{
	char t=GC;int x;
	while(t<48||t>57)t=GC;
	for(x=0;t>47&&t<58;t=GC)x=(x<<3)+(x<<1)+t-48;
	return x;
}
inline char _S()
{
	char t=GC;
	while(t!='0'&&t!='1')t=GC;
	return t;
}
const int T=40;
struct node{int l,r,id;}K[N];
bool operator<(node a,node b)
{return a.r<b.r;}
int n,q,Ans[N];
int rt=1,tot=1,son[M][2],las[M],Max[T+5];
char s[N];
void ADD(int x)
{
	int p=rt;
	for(register int i=1;i<=T&&x+i-1<=n;i++)
	{
		int t=s[x+i-1]-48;
		if(!son[p][t])son[p][t]=++tot;
		p=son[p][t];
		if(las[p])Max[i]=max(Max[i],las[p]);
		las[p]=x;
	}
}
int main()
{
	int x,y,ans;
	n=_R();q=_R();
	for(register int i=1;i<=n;i++)s[i]=_S();
	for(register int i=1;i<=q;i++)
	{
		x=_R();y=_R();
		K[i]=(node){x,y,i};
	}
	sort(K+1,K+q+1);
	for(register int i=1,j=1;i<=q;i++)
	{
		while(j<=K[i].r)ADD(j++);
		x=K[i].l;ans=0;
		for(register int k=T;k>=1;k--)
		if(Max[k]>=x)ans+=(Max[k]-x+1)*k,x=Max[k]+1;
		Ans[K[i].id]=ans;
	}
	for(register int i=1;i<=q;i++)printf("%d\n",Ans[i]);
}