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]
对于第二问，和第一问类似，处理一个前缀，然后需要二分。
1 #include <iostream> 2 #include <string.h> 3 #include <stdio.h> 4 #include <math.h> 5 #include <stdlib.h> 6 #include <queue> 7 using namespace std; 8 #define ll long long 9 ll a[110000],lt[110000],rt[110000],n; 10 ll dp[110000],dp1[110000],maxlen[110000]; 11 void fun(ll x) 12 { 13 int l,r,ans,m; 14 l=1,r=n,ans=-1; 15 while(l<=r) 16 { 17 m=(l+r)>>1; 18 if(x>dp1[m]) 19 { 20 l=m+1; 21 } 22 else 23 { 24 r=m-1; 25 ans=m; 26 } 27 } 28 printf("%d ",ans); 29 } 30 int main() 31 { 32 //freopen("in.txt","r",stdin); 33 int t,i,m; 34 ll x,y; 35 scanf("%d",&t); 36 while(t--) 37 { 38 scanf("%d%d",&n,&m); 39 a[n+1]=a[0]=-1; 40 for(i=1; i<=n; i++) 41 scanf("%lld",&a[i]); 42 for(i=1; i<=n; i++) 43 { 44 lt[i]=i; 45 while(a[i]<=a[lt[i]-1])lt[i]=lt[lt[i]-1]; 46 } 47 for(i=n; i>=1; i--) 48 { 49 rt[i]=i; 50 while(a[i]<=a[rt[i]+1])rt[i]=rt[rt[i]+1]; 51 } 52 memset(maxlen,0,sizeof(maxlen)); 53 for(i=1; i<=n; i++) 54 maxlen[rt[i]-lt[i]+1]=max(maxlen[rt[i]-lt[i]+1],a[i]); 55 for(i=n-1; i>=1; i--) 56 maxlen[i]=max(maxlen[i],maxlen[i+1]); 57 memset(dp,0,sizeof(dp)); 58 memset(dp1,0,sizeof(dp1)); 59 for(i=n; i>=1; i--) 60 dp[i]=max(dp[i+1],maxlen[i]*i); 61 for(i=1; i<=n; i++) 62 dp1[i]=max(dp1[i-1],maxlen[i]*i); 63 64 for(i=0; i<m; i++) 65 { 66 scanf("%lld%lld",&x,&y); 67 if(x==1) 68 { 69 if(y>n) 70 printf("-1 "); 71 else 72 { 73 if(y<=0) 74 y=1; 75 printf("%lld ",dp[y]); 76 } 77 78 } 79 else 80 { 81 fun(y); 82 } 83 } 84 } 85 }