Description

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

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

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

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

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

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

Solution

考虑暴力做法,离线询问

因为两个串的最长公共后缀,就是所代表节点的 \(lca\) 的 \(len\)

每一次加入一个前缀,在 \(parent\) 树上往上跳,如果一个点被跳过我们就更新答案

因为右端点固定时,左端点越大,对询问的贡献肯定越多,所以直接覆盖掉这个节点事件的下标(也就是 \(pos\)),所以我们维护这个节点子树内的最大 \(pos\) 值就行了

但是还有一个左端点限制,我们开一个左端点为下标的树状数组维护一下就好了

实际上这个过程就是 \(LCT\) 的 \(access\),那么用 \(LCT\) 做这个过程复杂度就可以均摊为 \(access\) 的复杂度了

#include<bits/stdc++.h>

using namespace std;

const int N=2e5+10;

template<class T>void gi(T &x){

	int f;char c;

	for(f=1,c=getchar();c<'0'||c>'9';c=getchar())if(c=='-')f=-1;

	for(x=0;c>='0'&&c<='9';c=getchar())x=x*10+(c&15);x*=f;

}

int fa[N],ch[N][2],len[N],cur=1,cnt=1,n,Q,pos[N];

char s[N];int tr[N],ans[N];

struct data{int x,id;};

vector<data>v[N];vector<data>::iterator it;

inline void add(int x,int y){for(int i=x;i>=1;i-=(i&(-i)))tr[i]=max(tr[i],y);}

inline int qry(int x){

	int ret=0;

	for(int i=x;i<=n;i+=(i&(-i)))ret=max(ret,tr[i]);

	return ret;

}

namespace lct{

	int fa[N],ch[N][2],w[N],la[N];

	inline void mark(int x,int y){w[x]=y;la[x]=y;}

	inline bool isrt(int x){return ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x;}

	inline void rotate(int x){

		int y=fa[x];bool t=ch[y][1]==x;

		ch[y][t]=ch[x][!t];fa[ch[y][t]]=y;

		ch[x][!t]=y;fa[x]=fa[y];

		if(!isrt(y))ch[fa[y]][ch[fa[y]][1]==y]=x;

		fa[y]=x;

	}

	inline void pushdown(int x){

		if(!la[x])return ;

		mark(ch[x][0],la[x]);mark(ch[x][1],la[x]);la[x]=0;

	}

	inline void Push(int x){if(!isrt(x))Push(fa[x]);pushdown(x);}

	inline void splay(int x){

		Push(x);

		while(!isrt(x)){

			int y=fa[x],p=fa[y];

			if(isrt(y))rotate(x);

			else if((ch[p][0]==y)==(ch[y][0]==x))rotate(y),rotate(x);

			else rotate(x),rotate(x);

		}

	}

	inline void access(int x,int id){

		int y=0;

		while(x)splay(x),ch[x][1]=y,add(w[x],len[x]),x=fa[y=x];

		mark(y,id);

	}

}

inline void ins(int c){

	int p=cur;cur=++cnt;len[cur]=len[p]+1;

	for(;p && !ch[p][c];p=fa[p])ch[p][c]=cur;

	if(!p)fa[cur]=1;

	else{

		int q=ch[p][c];

		if(len[p]+1==len[q])fa[cur]=q;

		else{

			int nt=++cnt;len[nt]=len[p]+1;

			memcpy(ch[nt],ch[q],sizeof(ch[q]));

			fa[nt]=fa[q];fa[cur]=fa[q]=nt;

			for(;p && ch[p][c]==q;p=fa[p])ch[p][c]=nt;

		}

	}

}

int main(){

  freopen("pp.in","r",stdin);

  freopen("pp.out","w",stdout);

  int x,y;

  cin>>n>>Q;

  scanf("%s",s+1);

  for(int i=1;i<=n;i++)ins(s[i]-'0'),pos[i]=cur;

  for(int i=1;i<=Q;i++)gi(x),gi(y),v[y].push_back((data){x,i});

  for(int i=2;i<=cnt;i++)lct::fa[i]=fa[i];

  for(int i=1;i<=n;i++){

	  lct::access(pos[i],i);

	  for(it=v[i].begin();it!=v[i].end();++it)ans[it->id]=qry(it->x);

  }

  for(int i=1;i<=Q;i++)printf("%d\n",ans[i]);

  return 0;

}