Border 的四种求法[BJWC2018]

发表于 2020-03-13 分类于 luogu

题目链接

链接

题意

求 $S[l,r]$ 的border。$n,m\leq 2\times 10^5$

题解

码农题。。

重要的性质

题目允许离线。
判断一个子串 $S[l,i]$ 是否是 $S[l,r]$ 的border的方法为：$i-l+1\leq lcp(i,r)$ 且 $i\in[l,r)$

分析做法

$lcp(i,r)$ 显然是SAM的fail树中 $i,r$ 的LCA的 $len$ 值。

假设我们枚举LCA，那么判断条件就变为 $i-l+1\leq len_{lca}$ ， $l\leq i < r$，也就是 $l\leq i \leq \min{len_{lca}+l-1,r-1}$。除此之外还要满足 $i$ 在 $lca$ 的子树内。

我们需要在 $lca$ 的子树中找到一个 $i$，使得满足上述条件且值最大。那么在fail树上用线段树合right集合，然后在线段树上二分就好了。

但是枚举 $lca$ 的复杂度是 $O(n)$ 的。

考虑树链剖分，然后进行链分治。

考虑在 $r$ 处一直向根跳，跳到的点就是需要进行枚举LCA的点。

显然他跳过最多 $\log n$ 条轻链。

对于每条重链而言，这个 $r$ 所经过的点的是一个前缀。

假设你现在只有一条重链，一个询问。那么分两类讨论：对于这个询问所在的点 $r$ 而言，能贡献给他的 $i$ 都满足在他的子树内，因此用上面所说的线段树合并去处理即可；对于这条重链中，在这个点 $r$ 上面的每个点 $j$，考虑哪些 $i$ 是能对这个 $j$ 有贡献的。显然只有 $j$ 本身，或者是他轻儿子的子树中的所有点。

假设你现在只有一条重链，很多个询问。那么就可以把询问离线，对于重链从上往下做：

考虑第二种情况怎么算。考虑最暴力的方法，将 $j$ 的所有轻儿子的子树的所有点赋予某个权值，然后加进去某个数据结构里，然后询问的时候在这个数据结构里搞搞。实际上这个暴力是没有问题的，因为一个点往上最多有 $\log n$ 条轻链，也就是最多会被加进数据结构里 $\log n$ 次。

再看看这个数据结构能是什么。这个点实际上有两个权值，一个是 $i+len_j-1$，另一个是 $i$。满足 $i-len_j+1\leq l$，且 $l\leq i \leq r-1$，需要找最大的 $i$。

~~那么用树套树随便搞一下就好了。~~有这种想法的怕不是数据结构学傻了（

用 $i$ 做下标，$i-len_j+1$ 做权值，开个线段树，询问的时候在线段树上记录一个区间最小值，在不超过 $\log n$ 个线段树的节点中用线段树上二分就可以了。

所以我们需要：SAM+树链剖分+线段树+线段树合并~~就可以了~~。

代码

也就4k嘛。接下来那篇更长。。。

#include <bits/stdc++.h>
using namespace std;
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define DEBUG(x) cout<<#x<<"="<<x<<endl;
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define ll long long
#define ull unsigned ll
#define db double
#define lb long db
#define pb push_back
#define mp make_pair
#define fi first
#define se second
inline int read()
{
	int x=0; char ch=getchar(); bool f=0;
	for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
	return f?-x:x;
}
const int N=4e5+5;
const int S=26;
const int M=7.5e6+5;
const int inf=2e9;
int ans[N>>1],n;

namespace S1{
	int ls[M],rs[M],mx[M],cnt;
	void ins(int &u,int l,int r,int p)
	{
		u=++cnt;
		if(l==r) return (void)(mx[u]=p);
		int mid=l+r>>1;
		p<=mid?ins(ls[u],l,mid,p):ins(rs[u],mid+1,r,p);
		mx[u]=max(mx[ls[u]],mx[rs[u]]);
	}
	int merge(int x,int y)
	{
		if(!x||!y) return x+y;
		int u=++cnt;
		ls[u]=merge(ls[x],ls[y]);
		rs[u]=merge(rs[x],rs[y]);
		mx[u]=max(mx[ls[u]],mx[rs[u]]);
		return u;
	}
	int query(int u,int l,int r,int L,int R)
	{
		if(!u||L>R) return 0;
		if(l==r) return mx[u];
		int mid=l+r>>1;
		if(mid<R&&rs[u])
		{
			int tmp=query(rs[u],mid+1,r,L,R);
			return tmp?tmp:query(ls[u],l,mid,L,R);
		}
		else return L<=mid?query(ls[u],l,mid,L,R):0;
	}
}
namespace S2{
	int mi[N<<2];
	#define lc (u<<1)
	#define rc (u<<1|1)
	#define ls lc,l,mid
	#define rs rc,mid+1,r
	void init(int n)
	{
		fo(i,0,n<<2) mi[i]=inf;
	}
	void add(int u,int l,int r,int p,int v)
	{
		if(p<l||p>r) return;
		if(l==r) {mi[u]=v; return;}
		int mid=l+r>>1;
		p<=mid?add(ls,p,v):add(rs,p,v);
		mi[u]=min(mi[lc],mi[rc]);
	}
	void del(int u,int l,int r,int p)
	{
		mi[u]=inf;
		if(l==r) return;
		int mid=l+r>>1;
		p<=mid?del(ls,p):del(rs,p);
	}

	int query(int u,int l,int r,int L,int R)
	{
		if(mi[u]>L) return 0;
		if(l==r) return mi[u]<=L?l:0;
		int mid=l+r>>1;
		if(mid<R&&mi[rc]<=L)
		{
			int tmp=query(rs,L,R);
			return tmp?tmp:query(ls,L,R);
		}
		else return L<=mid?query(ls,L,R):0;
	}
	#undef lc
	#undef rc
	#undef ls
	#undef rs
}

int p[N];
namespace Tree{
	struct node{
		int l,r,id;
	};
	vector<node> q[N];
	vector<int> adj[N];
	int siz[N],top[N],son[N],fa[N],val[N],rt[N];
	inline void add(int x,int y){adj[x].pb(y);}
	void dfs(int u)
	{
		siz[u]=1;
		if(p[u]) S1::ins(rt[u],1,n,p[u]);
		for(auto v:adj[u])
		{
			fa[v]=u;
			dfs(v);
			rt[u]=S1::merge(rt[u],rt[v]);
			siz[u]+=siz[v];
			if(siz[son[u]]<=siz[v]) son[u]=v;
		}
	}
	void dfs(int u,int tp)
	{
		top[u]=tp; if(son[u]) dfs(son[u],tp);
		for(auto v:adj[u]) if(v!=son[u]) dfs(v,v);
	}
	inline void jump(int x,int l,int r,int id)
	{
		for(;x;x=fa[top[x]]) q[x].pb((node){l,r,id});
	}

	void ins(int u,int len)
	{
		if(p[u]) S2::add(1,1,n,p[u],p[u]-len+1);
		for(auto v:adj[u]) ins(v,len);
	}
	void del(int u)
	{
		if(p[u]) S2::del(1,1,n,p[u]);
		for(auto v:adj[u]) del(v);
	}
	void solve(int u)
	{
		vector<int> vec;
		int l,r,id,tmp;
		vec.clear();
		for(int v=u;v;v=son[v]) vec.pb(v);
		for(auto v:vec)
		{
			if(p[v]) S2::add(1,1,n,p[v],p[v]-val[v]+1);
			for(auto w:adj[v]) if(son[v]!=w) ins(w,val[v]);
			for(auto qu:q[v])
			{
				l=qu.l,r=qu.r,id=qu.id;
				tmp=S1::query(rt[v],1,n,l,min(l+val[v]-1,r-1));
				if(l<=tmp&&tmp<r) ans[id]=max(ans[id],tmp-l+1);
				tmp=S2::query(1,1,n,l,r-1);
				if(l<=tmp&&tmp<r) ans[id]=max(ans[id],tmp-l+1);
			}
		}
		for(auto v:vec)
		{
			if(p[v]) S2::del(1,1,n,p[v]);
			for(auto w:adj[v]) if(son[v]!=w) del(w);
		}
		for(auto v:vec) for(auto w:adj[v]) if(son[v]!=w) solve(w);
	}
}
namespace SAM{
	int ne[N][S],len[N],fa[N],siz,las;
	void init()
	{
		siz=las=1;
	}
	inline int extend(int c,int id)
	{
		int p=las,cur=++siz;
		len[cur]=len[p]+1;
		for(;p&&!ne[p][c];p=fa[p]) ne[p][c]=cur;
		if(!p) fa[cur]=1;
		else
		{
			int q=ne[p][c];
			if(len[q]==len[p]+1) fa[cur]=q;
			else
			{
				int clone=++siz;
				memcpy(ne[clone],ne[q],sizeof(ne[q]));
				len[clone]=len[p]+1;
				fa[clone]=fa[q];
				for(;p&&ne[p][c]==q;p=fa[p]) ne[p][c]=clone;
				fa[q]=fa[cur]=clone;
			}
		}
		las=cur; ::p[las]=id;
		return las;
	}
	void build_tree()
	{
		fo(i,2,siz) Tree::add(fa[i],i);
		fo(i,1,siz) Tree::val[i]=len[i];
	}
}
char s[N>>1];
int m,pos[N];
void init()
{
	scanf("%s",s+1);
	SAM::init();
	n=strlen(s+1);
	fo(i,1,n) pos[i]=SAM::extend(s[i]-'a',i);
	SAM::build_tree();
	Tree::dfs(1);
	Tree::dfs(1,1);
	S2::init(n);
}
void work()
{
	m=read();
	int l,r;
	fo(i,1,m)
	{
		l=read(); r=read();
		Tree::jump(pos[r],l,r,i);
	}
	Tree::solve(1);
	fo(i,1,m) printf("%d\n",ans[i]);
}
int main()
{
	init(); work();
	return 0;
}