玲珑杯 Round15 G咸鱼拷问

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

很明显的线段树题目，区间查询不涉及更新，只是竟然可以暴力过有点奇葩。

暴力1979ms，线段树200ms，还是有差别的

代码：

 1 const int inf = 0x3f3f3f3f;
 2 #define maxn 100005
 3 #define maxnode 300005
 4 struct node{
 5     int left, right;
 6     int val;
 7 };
 8 node tree_min[maxnode], tree_max[maxnode];
 9 int a[maxn], b[maxn];
10 int n;
11 
12 int buildTree_min(int l, int r, int node_num){
13     if(l == r){
14         tree_min[node_num] = (node){l, r, a[l]};
15         return a[l];
16     }
17     int mid = l + r;
18     mid >>= 1;
19     int lv = buildTree_min(l, mid, node_num << 1);
20     int rv = buildTree_min(mid + 1, r, node_num << 1 | 1);
21     int tmres = min(lv, rv);
22     tree_min[node_num] =  (node){l, r, tmres};
23     return tmres;
24 }
25 int buildTree_max(int l, int r, int node_num){
26     if(l == r){
27         tree_max[node_num] = (node){l, r, a[l]};
28         return a[l];
29     }
30     int mid = l + r;
31     mid >>= 1;
32     int lv = buildTree_max(l, mid, node_num << 1);
33     int rv = buildTree_max(mid + 1, r, node_num << 1 | 1);
34     int tmres = max(lv, rv);
35     tree_max[node_num] =  (node){l, r, tmres};
36     return tmres;
37 }
38 int rmq_min(int ql, int qr, int l, int r, int node_num){
39     if(ql == l && qr == r)
40         return tree_min[node_num].val;
41     int mid = l + r;
42     mid >>= 1;
43     if(ql > mid){
44         return rmq_min(ql, qr, mid + 1, r, node_num << 1 | 1);
45     } 
46     else if(qr > mid){
47         int lv = rmq_min(ql, mid, l, mid, node_num << 1);
48         int rv = rmq_min(mid + 1, qr, mid + 1, r, node_num << 1 | 1);
49         return min(lv, rv);
50     }
51     else{
52         return rmq_min(ql, qr, l, mid, node_num << 1);
53     }
54 }
55 int rmq_max(int ql, int qr, int l, int r, int node_num){
56     if(ql == l && qr == r)
57         return tree_max[node_num].val;
58     int mid = l + r;
59     mid >>= 1;
60     if(ql > mid){
61         return rmq_max(ql, qr, mid + 1, r, node_num << 1 | 1);
62     } 
63     else if(qr > mid){
64         int lv = rmq_max(ql, mid, l, mid, node_num << 1);
65         int rv = rmq_max(mid + 1, qr, mid + 1, r, node_num << 1 | 1);
66         return max(lv, rv);
67     }
68     else{
69         return rmq_max(ql, qr, l, mid, node_num << 1);
70     }
71 }
72 
73 
74 int main(){
75     scanf("%d", &n);
76     for(int i = 0; i < n; i++)
77         scanf("%d", &a[i]);
78     for(int i = 0; i < n; i++)
79         scanf("%d", &b[i]);
80     buildTree_min(0, n - 1, 1);
81     buildTree_max(0, n - 1, 1);
82     for(int i = 0; i < n; i++){
83         long long ans = 0;
84         int tmmin = inf, tmmax = -inf;
85         tmmin = rmq_min(i - b[i] + 1, i, 0, n - 1, 1);
86         tmmax = rmq_max(i - b[i] + 1, i, 0, n - 1, 1);
87         ans = tmmin * (long long)tmmax;
88         printf("%lld
", ans);
89     }
90 }

题目：

1128 - 咸鱼拷问

Time Limit：3s Memory Limit：128MByte

Submissions：322Solved：94

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