记录编号	370764	评测结果	AAAAAAAAAAA
题目名称	[HEOI 2016] 字符串	最终得分	100
用户昵称	yourfather	是否通过	通过
代码语言	C++	运行时间	8.759 s
提交时间	2017-02-14 14:21:26	内存使用	68.38 MiB

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
const int maxn = 100100;
struct Node{
	int lch,rch,val;
	Node(){lch = rch = val = 0;}
}t[maxn*50];
int tot = 0,root[maxn]={0},cnt = 0;;
int sa[maxn],wa[maxn],wb[maxn],bucket[maxn];
int rank[maxn]={0},height[maxn]={0};
int st[20][maxn]={0},Log2[maxn]={0};
bool Cmp(const int *r,int x,int y,int k)
{return r[x] == r[y]&&r[x+k] == r[y+k];}
void doubling(const char *r,int n,int m){
	int *x=wa,*y=wb,*t,i,j,p;
	for(i = 0;i <= m;i++)bucket[i] = 0;
	for(i = 0;i < n;i++)bucket[x[i] = r[i]]++;
	for(i = 1;i < m;i++)bucket[i] += bucket[i-1];
	for(i = n-1;i>=0;i--)sa[--bucket[x[i]]] = i;
	for(j = 1,p = 1;p < n;j<<=1,m=p){
		for(p=0,i=n-j;i<n;i++)y[p++] = i;
		for(i = 0;i < n;i++)if(sa[i] >= j)y[p++] = sa[i]-j;
		for(i = 0;i <= m;i++)bucket[i] = 0;
		for(i = 0;i < n;i++)bucket[x[y[i]]]++;
		for(i = 1;i <= m;i++)bucket[i]+=bucket[i-1];
		for(i = n-1;i>=0;i--)sa[--bucket[x[y[i]]]] = y[i];
		for(t=x,x=y,y=t,x[sa[0]] = 0,p=1,i=1;i < n;i++)
			x[sa[i]] = Cmp(y,sa[i],sa[i-1],j)?p-1:p++;
	}
}
void Getheight(const char *r,int n){
	int i,j,k = 0;
	for(i = 0;i <= n;i++)rank[sa[i]] = i;
	for(i = 0;i <= n;height[rank[i++]] = k)
		for(k?k--:0,j = sa[rank[i]-1];r[i+k] == r[j+k];k++);
}
int N,M;char ch[maxn];
void Init(){
	memset(st,0x3f,sizeof(st));
	Log2[1] = 0;
	for(int i = 2;i <= N;i++){
		Log2[i] = Log2[i-1];
		if((1<<Log2[i]+1) == i)Log2[i]++;
	}
	memset(st,0x3f,sizeof st);
	for(int i = 0;i <= N;i++)st[0][i]=height[i+1];
	for(int i = 1;i <= Log2[N];i++)
		for(int j = 0;j <= N;j++){
			st[i][j]=st[i-1][j];
			if(j+(1<<i-1) <= N)st[i][j] = min(st[i][j],st[i-1][j+(1<<i-1)]);
		}
}
int Rmq(int l,int r){
	if(l > r)swap(l,r);r--;
	int len = Log2[r-l+1];
	return min(st[len][l],st[len][r-(1<<len)+1]);
}
void Insert(int last,int &now,int l,int r,int goal){
	now = ++tot;
	t[now] = t[last];t[now].val++;
	if(l == r)return;
	int mid = (l+r)>>1;
	if(goal <= mid)Insert(t[last].lch,t[now].lch,l,mid,goal);
	else Insert(t[last].rch,t[now].rch,mid+1,r,goal);
}
int query(int &L,int &R,int l,int r,int x,int y){
	if(!L)L = ++tot;if(!R)R = ++tot;
	if(x <= l&&y >= r)return t[R].val-t[L].val;
	int mid = (l+r)>>1,ret = 0;
	if(x <= mid)ret += query(t[L].lch,t[R].lch,l,mid,x,y);
	if(y >  mid)ret += query(t[L].rch,t[R].rch,mid+1,r,x,y);
	return ret;
}
#define mid ((l+r)>>1)
int Rank(int goal,int l,int r,int L,int R){
	int ret = 1;
	while(l < r){
		//if(l == r){printf("goal = %d,l = %d\n",goal,l);break;}
		if(goal <= mid){
			r = mid;
			L = t[L].lch;R = t[R].lch;
		}
		else{
			l = mid+1;
			ret += t[t[R].lch].val-t[t[L].lch].val;
			L = t[L].rch;R = t[R].rch;
		}
	}return ret;
}
int Kth(int x,int l,int r,int L,int R){
	while(l <= r){

		if(l == r)return l;
		int tmp = t[t[R].lch].val-t[t[L].lch].val;	
		if(tmp < x)x -= tmp,L = t[L].rch,R = t[R].rch,l = mid+1;
		else L = t[L].lch,R = t[R].lch,r = mid;
	}if(l == 0)puts("NO");
}
int Calc(int L,int R,int goal){
	int rr = Rank(goal,1,N,root[L],root[R+1]);//cout<<"rr is "<<rr<<endl;
	int qx=0,qy=0;
	if(R-L+2!=rr)qy = Kth(rr,1,N,root[L],root[R+1]);
	qx = Kth(rr-1,1,N,root[L],root[R+1]);
//	printf("qx = %d,qy = %d goal = %d\n",qx,qy,goal);
	return max(Rmq(qx,goal),Rmq(qy,goal));
}
int main(){
	freopen("heoi2016_str.in","r",stdin);
	freopen("heoi2016_str.out","w",stdout);
	scanf("%d%d%s",&N,&M,ch);
	doubling(ch,N+1,200);
	Getheight(ch,N);
	Init();
	for(int i = 0;i < N;i++)Insert(root[i],root[i+1],1,N,rank[i]);
	//for(int i = 0;i < N;i++)printf("%d ",rank[i]);printf("\n");
	int a,b,c,d;
	for(int i = 1;i <= M;i++){
		scanf("%d%d%d%d",&a,&b,&c,&d);a--;b--;c--;d--;
		int l = 0,r = min(b-a+1,d-c+1),ans=0;
		while(l <= r){
			if(Calc(a,b-mid+1,rank[c]) >= mid)ans = max(mid,ans),l = mid+1;
			else r = mid-1;
		}
		printf("%d\n",ans);
	}
	return 0;
}