即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

1128 – 咸鱼拷问(典型RMQ)

编程语言 qq_34287501 8℃ 0评论

题目链接:http://www.ifrog.cc/acm/problem/1128

1128 – 咸鱼拷问

Time Limit:3s Memory Limit:128MByte

Submissions:353Solved:106

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


解析:两边RMQ即可,完全套板子

代码:

#include
#define N 100009
using namespace std;

int di[N][33], da[N][33], n;


void RMQ_min()
{
    for(int j = 1; j <= 20; j++)
    {
        for(int i = 1; i <= n; i++)
        {
            if(i+(1<>1)][j-1]);
        }
    }
}

void RMQ_max()
{
    for(int j = 1; j <= 20; j++)
    {
        for(int i = 1; i <= n; i++)
        {
            if(i+(1<>1)][j-1]);
        }
    }
}



int main()
{

    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
    {
        scanf("%d", &di[i][0]);
        da[i][0] = di[i][0];
    }
    RMQ_min();
    RMQ_max();
    int L, R, k;
    for(int i = 1; i <= n; i++)
    {
        scanf("%d", &L);
        L = i - L + 1;
        R = i;
        k = (int)(log(1.0*R - L + 1) / log(2.0));
        long long a = min(di[L][k], di[R - (1<






转载请注明:CodingBlog » 1128 – 咸鱼拷问(典型RMQ)

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情