当前位置：首页 > 移动开发 > 正文

hdu6406 Taotao Picks Apples 多校第8场1010

yunbo1
移动开发
2026-09-10
112

Problem Description

There is an apple tree in front of Taotao‘s house. When autumn comes,

Input

The first line of input is a single line of integer

Output

For each query, display the answer in a single line.

Sample Input

5 3

1 2 3 4 4

1 5

5 5

2 3

Sample Output

Hint

For the first query, the heights of the apples were 5, 2, 3, 4, 4, so Taotao would only pick the first apple.

For the second query, the heights of the apples were 1, 2, 3, 4, 5, so Taotao would pick all these five apples.

For the third query, the heights of the apples were 1, 3, 3, 4, 4, so Taotao would pick the first, the second and the fourth apples.

预处理在RMQ+二分，挺好的题目。

dp1,为前缀，dp2为后缀。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int N = 1e5+10;
 4 int dmax[N][25],a[N], cnt[N], dp1[N], dp2[N];
 5 int que[N], t, v, l, n, m;
 6 void init(){
 7     for(int i = 1; i <= n; i ++){
 8         dmax[i][0] = a[i];
 9     }
10     for(int j = 1; (1<<j) <= n; j ++){
11         for(int i = 1; i+(1<<j)-1<= n; i ++){
12             dmax[i][j] = max(dmax[i][j-1],dmax[(1<<(j-1))+i][j-1]);
13         }
14     }
15 }
16 int getValue(int l, int r){
17     int k = 0;
18     while(1<<(k+1) <= (r-l+1))k++;
19     return max(dmax[l][k],dmax[r-(1<<k)+1][k]);
20 }
21 int find(int l, int r, int x) {
22     int pos = -1;
23     while(l <= r) {
24         int m = (l+r) >> 1;
25         if(getValue(l, m) > x) {
26             pos = m;
27             r = m-1;
28         } else l = m+1;
29     }
30     return pos;
31 }
32 
33 int main() {
34     scanf("%d", &t);
35     while(t--) {
36         scanf("%d%d", &n, &m);
37         int mx = 0;
38         for(int i = 1; i <= n; i ++) {
39             scanf("%d", &a[i]);
40             if(mx < a[i]) {
41                 mx = a[i];
42                 dp1[i] = dp1[i-1]+1;
43             } else dp1[i] = dp1[i-1];
44             cnt[i] = max(a[i], cnt[i-1]);
45         }
46         init();
47         int tail = 0, head = 1;
48         for(int i = n; i >= 1; i --) {
49             while(head <= tail && que[tail] <= a[i]) tail --;
50             que[++tail] = a[i];
51             dp2[i] = (tail- head + 1);
52         }
53         while(m--) {
54             scanf("%d%d", &l, &v);
55             int ans = dp1[l-1];
56             if(v > cnt[l-1]) ++ ans;
57             v = max(v, cnt[l-1]);
58             int pos = find(l+1, n, v);
59             if(pos != -1) ans += dp2[pos];
60             printf("%d\n",ans);
61         }
62     }
63     return 0;
64 }