记录编号	401829	评测结果	AAAAAAAAAA
题目名称	[HAOI 2017]供给侧改革	最终得分	100
用户昵称	Cydiater	是否通过	通过
代码语言	C++	运行时间	2.854 s
提交时间	2017-05-04 08:06:05	内存使用	40.46 MiB

//HAOI2017 R1T2
//by Cydiater
//2017.5.3
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define up(i,j,n)	for(int i=j;i<=n;i++)
#define down(i,j,n)	for(int i=j;i>=n;i--)
#define cmax(a,b)	a=max(a,b)
#define cmin(a,b)	a=min(a,b)
#define FILE		"supply"

const int MAXN=1e5+5;
const int oo=0x3f3f3f3f;

int N,Q,q[MAXN],top,Wave[MAXN][45][2];//0->L 1->R
int ans[MAXN],Longer[45];
char s[MAXN];

struct Query{
	int L,R,p;
	bool operator < (const Query &a) const {
		return R<a.R;
	}
}qry[MAXN];

namespace SA{
	int sa[MAXN],rnk[MAXN],tmp[MAXN],hei[MAXN],p[MAXN],cnt[MAXN];
	inline bool equ(int x,int y,int l){return rnk[x]==rnk[y]&&rnk[x+l]==rnk[y+l];}
	void Build(){
		up(i,1,N){
			sa[i]=i;
			rnk[i]=s[i];
		}
		for(int sig=255,pos,l=0;pos<N;sig=pos){
			pos=0;
			up(i,N-l+1,N)p[++pos]=i;
			up(i,1,N)if(sa[i]>l)p[++pos]=sa[i]-l;
			up(i,0,sig)cnt[i]=0;
			up(i,1,N)cnt[rnk[i]]++;
			up(i,1,sig)cnt[i]+=cnt[i-1];
			down(i,N,1)sa[cnt[rnk[p[i]]]--]=p[i];
			pos=0;
			up(i,1,N)tmp[sa[i]]=equ(sa[i],sa[i-1],l)?pos:++pos;
			up(i,1,N)rnk[i]=tmp[i];
			l=!l?1:(l<<1);
		}
		int j=0,k=0;
		up(i,1,N){
			if(!(k=sa[rnk[i]-1])){j=0;continue;}
			if(j)j--;
			while(s[i+j]==s[k+j])j++;
			hei[rnk[i]]=j;
		}
	}
	void Mark(){
		memset(Wave,-1,sizeof(Wave));
		top=0;
		up(i,2,N){
			while(top>0&&hei[i]<=hei[q[top]])top--;
			if(!top||hei[i]>hei[q[top]])q[++top]=i;
			up(j,2,top)Wave[i][hei[q[j]]][0]=q[j-1];
			if(top>=1)Wave[i][hei[q[1]]][0]=1;
		}
		top=0;
		down(i,N-1,1){
			while(top>0&&hei[i+1]<=hei[q[top]+1])top--;
			if(!top||hei[i+1]>hei[q[top]+1])q[++top]=i;
			up(j,2,top)Wave[i][hei[q[j]+1]][1]=q[j-1];
			if(top>=1)Wave[i][hei[q[1]+1]][1]=N;
		}
	}
}using namespace SA;

namespace SegTree{
	int t[MAXN<<2];
	inline void reload(int k){
		t[k]=max(t[k<<1],t[k<<1|1]);
	}
	void Modify(int leftt,int rightt,int k,int p,int val){
		if(leftt==rightt){
			t[k]=val;
			return;
		}
		int mid=(leftt+rightt)>>1;
		if(p<=mid)	Modify(leftt,mid,k<<1,p,val);
		else		Modify(mid+1,rightt,k<<1|1,p,val);
		reload(k);
	}
	int Query(int leftt,int rightt,int k,int L,int R){
		if(leftt>=L&&rightt<=R)	return t[k];
		int mid=(leftt+rightt)>>1,mx=-oo;
		if(L<=mid)cmax(mx,Query(leftt,mid,k<<1,L,R));
		if(R>=mid+1)cmax(mx,Query(mid+1,rightt,k<<1|1,L,R));
		return mx;
	}
}

namespace solution{
	void Prepare(){
		scanf("%d%d",&N,&Q);
		scanf("%s",s+1);
		Build();
		Mark();
		up(i,1,Q){
			int L,R;
			scanf("%d%d",&L,&R);
			qry[i]=(Query){L,R,i};
		}
		sort(qry+1,qry+Q+1);
	}
	void Solve(){
		memset(Longer,0,sizeof(Longer));
		int p=1,mx;
		SegTree::Modify(1,N,1,rnk[1],1);
		up(i,2,N){
			up(j,0,40)if(Wave[rnk[i]][j][0]!=-1){
				mx=SegTree::Query(1,N,1,Wave[rnk[i]][j][0],rnk[i]);
				cmax(Longer[j],mx);
			}
			up(j,0,40)if(Wave[rnk[i]][j][1]!=-1){
				mx=SegTree::Query(1,N,1,rnk[i],Wave[rnk[i]][j][1]);
				cmax(Longer[j],mx);
			}
			down(j,40,0)cmax(Longer[j],Longer[j+1]);
			while(p<=Q&&i==qry[p].R){
				up(j,0,40){
					if(Longer[j+1]>=qry[p].L)	ans[qry[p].p]+=j*(Longer[j]-Longer[j+1]);
					else{
						ans[qry[p].p]+=j*(Longer[j]-qry[p].L+1);
						break;
					}
				}
				p++;
			}
			SegTree::Modify(1,N,1,rnk[i],i);
		}
		up(i,1,Q)printf("%d\n",ans[i]);
	}
}

int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	using namespace solution;
	Prepare();
	Solve();
	return 0;
}