Sequence query

Time Limit: 

2000/1000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)

Submit

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 21 21 22 1

Sample Output

21

用单调栈预处理出当以 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 
        
          2 #include 
         
           3 #include 
          
            4 #include 
           
             5 #include 
            
              6 #include 
             
               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 else23 {24 r=m-1;25 ans=m;26 }27 }28 printf("%d\n",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
              
               n)70 printf("-1\n");71 else72 {73 if(y<=0)74 y=1;75 printf("%lld\n",dp[y]);76 }77 78 }79 else80 {81 fun(y);82 }83 }84 }85 }