玲珑oj 1128 RMQ模板

1128 - 咸鱼拷问

Time Limit：3s Memory Limit：128MByte

Submissions：380Solved：118

DESCRIPTION

给你两个序列A,B。每个序列有N个元素，我们定义第i个位置的咸鱼值为min(A[i],A[i-1]…A[i-B[i]+1])*max(A[i],A[i-1]….A[i-B[i]+1]).。
现在咸鱼王想知道所有的咸鱼值，于是抓住了你，让你回答这道题。
你能回答他吗？

INPUT

第一行包括一个整数N（1<=N<=1e5）
第二行包括N个整数，表示为A[i] (|A[i]| <= 10^9)
第三行包括N个整数，表示为B[i] ( 1 <= B[i] <= i)

OUTPUT

输出N行，第i行表示第i个咸鱼值。

SAMPLE INPUT

5
1 2 3 4 5
1 2 1 2 3

SAMPLE OUTPUT

1
2
9
12
15

SOLUTION

“玲珑杯”线上赛 Round #15 河南专场

求最值且不需要更新，RMQ能做到 NlogN的预处理 O（1）的查询，直接套模板

注意查询区间为[0,N)

 

 #include<bits/stdc++.h>

 using namespace std;

 #define LL long long

 #define MAXN ((100000<<2)+15)

 int A[],B;

 int d[][][];

 void rmq(int n)

 {

     for(int i=;i<n;++i) d[][i][]=d[][i][]=A[i];

     for(int j=;(<<j)<=n;++j){

         for(int i=;i+(<<j)-<n;++i){

         d[][i][j]=min(d[][i][j-],d[][i+(<<(j-))][j-]);

         d[][i][j]=max(d[][i][j-],d[][i+(<<(j-))][j-]);

         }

     }

 }

 int RMQ(int L,int R,int x)

 {

     int k=;

     while((<<(k+))<=R-L+) k++;

     if(x==) return min(d[][L][k],d[][R-(<<k)+][k]);

     else     return max(d[][L][k],d[][R-(<<k)+][k]);

 }

 int main()

 {

     int t,n,m,i,j,k,opt,l,r,v;

     scanf("%d",&n);

     for(i=;i<n;++i) scanf("%d",&A[i]);

     rmq(n);

     for(i=;i<n;++i) {

             scanf("%d",&B);

     printf("%lld\n",(LL)RMQ(i+-B,i,)*RMQ(i+-B,i,));

     }

     return ;

 }