[LOJ6041]事情的相似度 - A-Failure的博客

题目

题目描述

人的一生不仅要靠自我奋斗，还要考虑到历史的行程。

历史的行程可以抽象成一个 01 串，作为一个年纪比较大的人，你希望从历史的行程中获得一些姿势。

你发现在历史的不同时刻，不断的有相同的事情发生。比如，有两个人同时在世纪之交 11 年的时候上台，同样喜欢与洋人谈笑风生，同样提出了以「三」字开头的理论。

你发现，一件事情可以看成是这个 01 串的一个前缀，这个前缀最右边的位置就是这个事情的结束时间。

两件事情的相似度可以看成，这两个前缀的最长公共后缀长度。

现在你很好奇，在一段区间内结束的事情中最相似的两件事情的相似度是多少呢？

输入格式

第一行两个整数 $n$、$m$，表示串长和询问个数。第二行长度为 $n$ 的 01 串，表示历史的行程。接下来 $m$ 行，每行两个正整数 $l$、$r$ 表示询问的区间，包括端点，保证 $1 \leq l < r \leq n$。

输出格式

输出 $m$ 行，对每个询问输出一个整数表示最大的相似度。

样例

样例输入 1

样例输出 1

1
2

数据范围与提示

测试点	$n =$	$m =$
1 ~ 2	$100$	$100$
3 ~ 4	$300$	$1000$
5 ~ 6	$5000$	$5000$
7 ~ 10	$100000$	$300$
11 ~ 14	$50000$	$50000$
15 ~ 20	$100000$	$100000$

题解

因为两个状态的$lcs$（最长公共后缀Longest Common Suffix）就是ta们在后缀树上$lca$的$len$，所以题目就是要求一个区间内两点的$len_{lca}$最大是多少

对于某个点，能让ta作为答案的只有ta的不同子树里的点或者ta自己和子树中的某个点

所以可以启发式合并，记录一下当前枚举点在原序列中最接近的点，记录下来，这个用set可以维护了

把询问离线，按右端点排序，然后扫描线即可

代码

# include<iostream>
# include<cstring>
# include<cstdio>
# include<set>
# include<algorithm>
# define tl (k<<1)
# define tr (k<<1|1)
# define mid (l+r>>1)
using namespace std;
const int MAX=2e5+5;
struct p{
	int x,y,L;
	bool operator< (const p &a)
	const{
		return y<a.y;
	}
}b[MAX<<4];
struct q{
	int l,r,id;
	bool operator< (const q &a)
	const{
		return r<a.r;
	}
}qu[MAX];
struct o{
	int x;
}s[MAX<<1];
int n,cnt,Q;
int ans[MAX];
char a[MAX];
struct SAM{
	struct u{
		int x,y;
	}c[MAX];
	int l,r,L,num;
	int h[MAX],len[MAX],fa[MAX];
	int son[MAX][2];
	set<int> s[MAX];
	SAM() {l=r=1;}
	void add(int x,int y) {c[++num]=(u){h[x],y},h[x]=num;}
	void ins(int x,int id)
	{
		int tt=r;
		len[r=++l]=++L,s[r].insert(id);
		for(;tt&&!son[tt][x];tt=fa[tt])
		  son[tt][x]=r;
		if(!tt) return void(fa[r]=1);
		int qwq=son[tt][x];
		if(len[qwq]==len[tt]+1) return void(fa[r]=qwq);
		len[++l]=len[tt]+1,fa[l]=fa[qwq],fa[qwq]=fa[r]=l,son[l][0]=son[qwq][0],son[l][1]=son[qwq][1];
		for(int i=tt;son[i][x]==qwq;i=fa[i])
		  son[i][x]=l;
	}
	void dfs(int x=1)
	{
		for(int i=h[x];i;i=c[i].x)
		  {
		  	dfs(c[i].y);
		  	if(!len[x]) continue;
		  	if(s[x].size()<s[c[i].y].size()) swap(s[x],s[c[i].y]);
		  	for(set<int>::iterator A=s[c[i].y].begin(),B;A!=s[c[i].y].end();++A)
		  	  {
		  	  	B=s[x].upper_bound(*A);
				if(B!=s[x].end()) b[++cnt]=(p){*A,*B,len[x]};
		  	  	if(B!=s[x].begin()) b[++cnt]=(p){*(--B),*A,len[x]};
			  }
			for(set<int>::iterator A=s[c[i].y].begin();A!=s[c[i].y].end();++A)
			  s[x].insert(*A);
		  }
	}
	void Init()
	{
		for(int i=2;i<=l;++i)
		  add(fa[i],i);
		dfs(),sort(b+1,b+1+cnt);
	}
}_S;
int read()
{
	int x(0);
	char ch=getchar();
	for(;!isdigit(ch);ch=getchar());
	for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
	return x;
}
void change(int l,int r,int k,int x,int dis)
{
	s[k].x=max(s[k].x,dis);
	if(l==r) return;
	if(x<=mid) change(l,mid,tl,x,dis);
	else change(mid+1,r,tr,x,dis);
}
int ask(int l,int r,int k,int L,int R)
{
	if(r<L||R<l) return 0;
	if(l>=L&&r<=R) return s[k].x;
	return max(ask(l,mid,tl,L,R),ask(mid+1,r,tr,L,R));
}
int main()
{
	n=read(),Q=read(),scanf("%s",a+1);
	for(int i=1;i<=n;++i)
	  _S.ins(a[i]-'0',i);
	_S.Init();
	for(int i=1;i<=Q;++i)
	  qu[i].l=read(),qu[i].r=read(),qu[i].id=i;
	sort(qu+1,qu+1+Q);
	for(int i=1,L=1;i<=Q;++i)
	  {
	  	while(b[L].y<=qu[i].r&&L<=cnt) change(1,n,1,b[L].x,b[L].L),++L;
	  	ans[qu[i].id]=ask(1,n,1,qu[i].l,qu[i].r);
	  }
	for(int i=1;i<=Q;++i)
	  printf("%d\n",ans[i]);
	return 0;
}

题目