ZSTUOJ 4239 巴比伦花园

好题。

先对于每个位置，求出向右延伸的最大长度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

*/