题目链接：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 SOLUTION “玲珑杯”ACM比赛 Round #15 Submit summary Discuss解析：两边RMQ即可，完全套板子
代码：
#include<bits/stdc++.h> #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<<j) - 1 <= n) di[i][j] = min(di[i][j-1], di[i + (1<<j>>1)][j-1]); } } } void RMQ_max() { for(int j = 1; j <= 20; j++) { for(int i = 1; i <= n; i++) { if(i+(1<<j) - 1 <= n) da[i][j] = max(da[i][j-1], da[i + (1<<j>>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<<k) + 1][k]); long long b = max(da[L][k], da[R - (1<<k) + 1][k]); long long ans = a * b; printf("%lld\n", ans); } return 0; }
