好题。
先对于每个位置，求出向右延伸的最大长度l[i]。
求法：把所有h[i]都减去i*k，然后就是求 以坐标(i,-i*k)为左下角的最长矩形 ， 可以用单调栈来做。
求完l[i]，问题就转化成了n条线段，q次询问，问区间内最长线段。
这些线段有个性质，就是右端点是相等或者递增的（也就是不下降）。像这样：
11111111
01111111
00111111
00011111
0000011111
0000001111
000000011111
假设询问[x,y],于是就可以二分找到第一个达到y的线段，然后就是在x和它之间求个区间最大值就好了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 | #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); } } }}/*10010 2 10005 3 9 8 100 2 10 6 8 291 1*/ |
