好题。

先对于每个位置，求出向右延伸的最大长度l[i]。

求法：把所有h[i]都减去i*k，然后就是求  以坐标(i,-i*k)为左下角的最长矩形 ，  可以用单调栈来做。

求完l[i]，问题就转化成了n条线段，q次询问，问区间内最长线段。

这些线段有个性质，就是右端点是相等或者递增的（也就是不下降）。像这样：

11111111

01111111

00111111

00011111

0000011111

0000001111

000000011111

假设询问[x,y],于是就可以二分找到第一个达到y的线段，然后就是在x和它之间求个区间最大值就好了。

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=100005;

int n,q;
ll k;
ll h[N];
int l[N];
ll stk[N],top;
int r[N];
int id[N];

struct ST
{
    int f[N][17]; //10w
    void make(int *a,int n)
    {
        for (int i=1;i<=n;i++) f[i][0]=a[i];
        for (int j=1;j<17;j++)
            for (int i=1;i<=n+1-(1<<j);i++)
                f[i][j]=max(f[i][j-1],f[i+(1<<j-1)][j-1]);
    }
    int get(int l,int r)
    {
        int k=log(r-l+1)/log(2);
        return max(f[l][k],f[r+1-(1<<k)][k]);
    }
}L;

int main()
{
	int t; scanf("%d",&t);
	while(t--)
	{
		scanf("%d%lld%d",&n,&k,&q);
		for (int i=1;i<=n;i++)
		{
			scanf("%lld",&h[i]);
			h[i]-=i*k;
		}
		top=0; id[0]=n+1;
		for (int i=n;i>=1;i--)
		{
			int pos=upper_bound(stk+1,stk+top+1,-i*k)-stk;
			pos--;
			l[i]=id[pos]-i;
			while(top&&h[i]<=stk[top]) top--;
			stk[++top]=h[i]; id[top]=i;
		}
		L.make(l,n);
		for (int i=1;i<=n;i++) r[i]=i+l[i]-1;
		while(q--)
		{
			int x,y;
			scanf("%d%d",&x,&y);
			if (x+l[x]>y) printf("%d\n",y-x+1);
			else
			{
				int pos=lower_bound(r+x+1,r+n+1,y)-r;
				int ret=min(r[pos],y)-pos+1;
				pos--;
				ret=max(ret,L.get(x,pos));
				printf("%d\n",ret);
			}
		}
	}
}
/*
100
10 2 1000
5 3 9 8 100 2 10 6 8 29
1 1

*/

枚举长度和起点，枚举起点的时候每次+长度。这样枚举的复杂度是O(nlogn)。

难点就在如何字典序最小。 可以求一下区间的rk的最小值来找这个字典序最小的位置。

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=100005;
char s[N],s2[N];
int len;

struct ST
{
	int f[N][17];
	void make(int *a,int n)
	{
		for (int i=1;i<=n;i++) f[i][0]=a[i];
		for (int j=1;j<17;j++)
			for (int i=1;i<=n+1-(1<<j);i++)
				f[i][j]=min(f[i][j-1],f[i+(1<<j-1)][j-1]);
	}
	int get(int l,int r)
	{
		int k=log(r-l+1)/log(2);
		return min(f[l][k],f[r+1-(1<<k)][k]);
	}
}HL,HR,RK;
struct suffixarray
{
	int sa[N],rk[N],h[N];
	int cnt[N],sa2[N],rk2[N];
	int n;
	bool cmp(int i,int j,int len)
	{
		if (rk2[i]==rk2[j]&&rk2[i+len]==rk2[j+len]) return 0;
		return 1;
	}
	void make(char *s,int len)
	{
		n=len;
		int m=255;
		for (int i=1;i<=m;i++) cnt[i]=0;
		for (int i=1;i<=n;i++) cnt[s[i]]++;
		for (int i=2;i<=m;i++) cnt[i]+=cnt[i-1];
		for (int i=n;i>=1;i--) sa[cnt[s[i]]--]=i;
		int k=1; rk[sa[1]]=1;
		for (int i=2;i<=n;i++)
		{
			if (s[sa[i]]!=s[sa[i-1]]) k++;
			rk[sa[i]]=k;
		}
		rk2[n+1]=0;
		for (int j=1;k<n&&j<=n;j*=2)
		{
			int tot=0;
			for (int i=n-j+1;i<=n;i++) sa2[++tot]=i;
			for (int i=1;i<=n;i++)
				if (sa[i]>j) sa2[++tot]=sa[i]-j;
			m=k;
			for (int i=1;i<=m;i++) cnt[i]=0;
			for (int i=1;i<=n;i++) cnt[rk[i]]++;
			for (int i=2;i<=m;i++) cnt[i]+=cnt[i-1];
			for (int i=n;i>=1;i--) sa[ cnt[rk[sa2[i]]]-- ]=sa2[i];
			for (int i=1;i<=n;i++) rk2[i]=rk[i];
			k=1; rk[sa[1]]=1;
			for (int i=2;i<=n;i++)
			{
				if (cmp(sa[i],sa[i-1],j)) k++;
				rk[sa[i]]=k;
			}
		}
		for (int i=1;i<=n;i++)
		{
			k=h[rk[i-1]];
			if (k>0) k--;
			int j=sa[rk[i]-1];
			while(s[i+k]==s[j+k]) k++;
			h[rk[i]]=k;
		}
	}
	int lcp(ST &H,int i,int j)
	{
		int l=rk[i],r=rk[j];
		if (l>r) swap(l,r);
		return H.get(l+1,r);
	}
}SAL,SAR;
int k,idx,sl;
void solve()
{
	k=1;
	idx=1;
	sl=1;
	for (int i=2;i<=len;i++)
		if (s[i]<s[idx]) idx=i;

	HL.make(SAL.h,len);
	HR.make(SAR.h,len);
	RK.make(SAL.rk,len);
	for (int j=1;j<=len/2;j++)
	{
		for (int i=1;i<=len-j;i+=j)
		{
			if (i+j*k-1>len) break;  // 卡常数
			if (s[i]!=s[i+j]) continue;  // 卡常数
			int r=i+j+SAL.lcp(HL,i,i+j)-1;
			int l=i-SAR.lcp(HR,len+1-i,len+1-(i+j))+1;
			if ((r-l+1)/j<k) continue;
			int re=(r-l+1)%j;
			int id=RK.get(l,l+re); // 这个区间都会出现重复k次的子串，在这个区间内找字典序最小来更新答案
			if ((r-l+1)/j>k||(r-l+1)/j==k&&id<idx)
				k=(r-l+1)/j,idx=id,sl=j;
			i=max(i,r+1-j);  // 卡常数
		}
	}
	s[SAL.sa[idx]+k*sl]=0;
	printf("%s",s+SAL.sa[idx]);
	printf("\n");
}
int main()
{
	int cas=0;
	while(scanf("%s",s+1),s[1]!='#')
	{
		printf("Case %d: ",++cas);
		len=strlen(s+1);
		for (int i=1;i<=len;i++) s2[len+1-i]=s[i];
		SAL.make(s,len);
		SAR.make(s2,len);
		solve();
	}
}