玲珑学院 1128 咸鱼拷问-白红宇

玲珑学院 1128 咸鱼拷问

阅读量：5359 次

发布时间：2019-06-15

本文共 978 字，大约阅读时间需要 3 分钟。

1128 - 咸鱼拷问

Time Limit：3s Memory Limit：128MByte

Submissions：367Solved：112

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

1 2 3 4 5

1 2 1 2 3

SAMPLE OUTPUT

15RMQ查询区间最值，线段树也可以

#include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 #include 
                  
                   using namespace std;#define lowbit(x) (x&(-x))#define max(x,y) (x>y?x:y)#define min(x,y) (x
                   
                    r) return 0; ll k=0; while(1<<(1+k)<=r-l+1) k++; return k;}ll rmqmax(ll l,ll r,ll k){ return max(maxx[l][k],maxx[r-(1<

转载于:https://www.cnblogs.com/shinianhuanniyijuhaojiubujian/p/7219656.html

你可能感兴趣的文章