记录编号	384290	评测结果	AAAAAAAAAAA
题目名称	[HEOI 2016] 字符串	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	4.926 s
提交时间	2017-03-17 21:38:10	内存使用	115.99 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn=200010,maxm=maxn<<5;
void expand(int);
void dfs(int);
void build(int,int,int&,int);
void query(int,int,int,int);
int sm[maxm]={0},lc[maxm]={0},rc[maxm]={0},root[maxn]={0},cnt=0;
int last,SAM_cnt=0,val[maxn]={0},par[maxn]={0},go[maxn][26]={{0}};
vector<int>G[maxn];
int dfn[maxn],finish[maxn],tim=0,f[maxn][20],depth[maxn];
char str[maxn>>1];
int n,m,lgn=0,iter[maxn>>1],a,b,c,d,s,t,tmp;
int main(){
	freopen("heoi2016_str.in","r",stdin);
	freopen("heoi2016_str.out","w",stdout);
	last=++SAM_cnt;
	scanf("%d%d%s",&n,&m,str+1);
	for(int i=n;i;i--){
		expand(str[i]-'a');
		iter[i]=last;
	}
	for(int i=2;i<=SAM_cnt;i++)G[par[i]].push_back(i);
	dfs(1);
	for(int i=1;i<=SAM_cnt;i++)f[i][0]=par[i];
	for(int j=1;j<=lgn;j++)for(int i=1;i<=SAM_cnt;i++)f[i][j]=f[f[i][j-1]][j-1];
	for(int i=1;i<=n;i++){
		t=dfn[iter[i]];
		build(1,tim,root[i],root[i-1]);
	}
	while(m--){
		scanf("%d%d%d%d",&a,&b,&c,&d);
		int L=1,R=min(val[iter[c]],min(d-c+1,b-a+1)),M,x;
		while(L<=R){
			M=(L+R)>>1;
			x=iter[c];
			for(int i=lgn;i>=0;i--)if(val[f[x][i]]>=M)x=f[x][i];
			s=dfn[x];t=finish[x];
			tmp=0;
			query(1,tim,root[b-M+1],root[a-1]);
			if(tmp)L=M+1;
			else R=M-1;
		}
		printf("%d\n",R);
	}
	return 0;
}
void expand(int c){
	int p=last,np=++SAM_cnt;
	val[np]=val[p]+1;
	while(p&&!go[p][c]){
		go[p][c]=np;
		p=par[p];
	}
	if(!p)par[np]=1;
	else{
		int q=go[p][c];
		if(val[q]==val[p]+1)par[np]=q;
		else{
			int nq=++SAM_cnt;
			val[nq]=val[p]+1;
			memcpy(go[nq],go[q],sizeof(go[q]));
			par[nq]=par[q];
			par[np]=par[q]=nq;
			while(p&&go[p][c]==q){
				go[p][c]=nq;
				p=par[p];
			}
		}
	}
	last=np;
}
void dfs(int x){
	dfn[x]=++tim;
	depth[x]=depth[par[x]]+1;
	while((1<<lgn)<depth[x])lgn++;
	for(int i=0;i<(int)G[x].size();i++)dfs(G[x][i]);
	finish[x]=tim;
}
void build(int l,int r,int &rt,int pr){
	sm[rt=++cnt]=sm[pr]+1;
	if(l==r)return;
	lc[rt]=lc[pr];
	rc[rt]=rc[pr];
	int mid=(l+r)>>1;
	if(t<=mid)build(l,mid,lc[rt],lc[pr]);
	else build(mid+1,r,rc[rt],rc[pr]);
}
void query(int l,int r,int rt,int pr){
	if(!rt&&!pr)return;
	if(s<=l&&t>=r){
		tmp+=sm[rt]-sm[pr];
		return;
	}
	int mid=(l+r)>>1;
	if(s<=mid)query(l,mid,lc[rt],lc[pr]);
	if(t>mid)query(mid+1,r,rc[rt],rc[pr]);
}