Sequence query
Problem Description
Given a sequence of N positive numbers，and M queries
A query maybe :
1 x，find the Maximun "weight" of the consecutive subsequence whose length >= x
2 x, find the Minimum length of the consecutive subsequence whose weight >= x
the weight of a consecutive subsequence Seq：weight(Seq) = length of Seq * minimum number in Seq.
Input
The first line is an integer T(1<=T<=100) ，the number of test cases;
For each test case，
the first line contains two integer N，M(1<=N,M<=100000)
the second line contains N positive integers(all between [1,2^31-1])
The following M lines contains queries as descripted above, all number is within signed ilong long
any subsequences should not be empty(length >= 1)
Output
for each query，output a line contains an answer you find，if the answer doesn't exist，output -1
Sample Input
1
2 2
1 2
1 2
2 1
Sample Output
2
1
用单调栈预处理出当以 a[i]为最小值的时候，最左向左延伸到哪里，最右向右延伸到哪里
不妨设为 lt[i],rt[i].
伪代码: a[0] = a[n + 1] = -1;
for(int i = 1; i <= n; i ++) {
lt[i] = i;
while(a[i] <= a[lt[i] - 1]) lt[i] = lt[lt[i] - 1];
}
rt[i]同样处理。当然，有很多种处理方法。
用 max_len[i]表示，当长度为 i 的时候，延伸长度不小于 i 的 ai 的最大值, for(int i = 1; i <= n; i ++) max_len[rt[i] - lt[i] + 1] = max(max_len[rt[i] - lt[i] + 1],a[i]);
max_len[i] = max(max_len[i],max_len[i + 1])
对于第一问，处理一个后缀，dp[i] = max(dp[i + 1],max_len[i] * i)
输入一个 x，判掉不合法的之后，直接输出 dp[x]
对于第二问，和第一问类似，处理一个前缀，然后需要二分。
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <queue>
using namespace std;
#define ll long long
ll a[],lt[],rt[],n;
ll dp[],dp1[],maxlen[];
void fun(ll x)
{
int l,r,ans,m;
l=,r=n,ans=-;
while(l<=r)
{
m=(l+r)>>;
if(x>dp1[m])
{
l=m+;
}
else
{
r=m-;
ans=m;
}
}
printf("%d\n",ans);
}
int main()
{
//freopen("in.txt","r",stdin);
int t,i,m;
ll x,y;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
a[n+]=a[]=-;
for(i=; i<=n; i++)
scanf("%lld",&a[i]);
for(i=; i<=n; i++)
{
lt[i]=i;
while(a[i]<=a[lt[i]-])lt[i]=lt[lt[i]-];
}
for(i=n; i>=; i--)
{
rt[i]=i;
while(a[i]<=a[rt[i]+])rt[i]=rt[rt[i]+];
}
memset(maxlen,,sizeof(maxlen));
for(i=; i<=n; i++)
maxlen[rt[i]-lt[i]+]=max(maxlen[rt[i]-lt[i]+],a[i]);
for(i=n-; i>=; i--)
maxlen[i]=max(maxlen[i],maxlen[i+]);
memset(dp,,sizeof(dp));
memset(dp1,,sizeof(dp1));
for(i=n; i>=; i--)
dp[i]=max(dp[i+],maxlen[i]*i);
for(i=; i<=n; i++)
dp1[i]=max(dp1[i-],maxlen[i]*i); for(i=; i<m; i++)
{
scanf("%lld%lld",&x,&y);
if(x==)
{
if(y>n)
printf("-1\n");
else
{
if(y<=)
y=;
printf("%lld\n",dp[y]);
} }
else
{
fun(y);
}
}
}
}