宝剑锋从磨砺出,梅花香自苦寒来。这篇文章主要讲述hdu6406 Taotao Picks Apples 多校第8场1010相关的知识,希望能为你提供帮助。
Problem Description
There is an apple tree in front of Taotao‘s house. When autumn comes,
n
apples on the tree ripen, and Taotao will go to pick these apples.
When Taotao picks apples, Taotao scans these apples from the first one to the last one. If the current apple is the first apple, or it is strictly higher than the previously picked one, then Taotao will pick this apple;
otherwise, he will not pick.
Given the heights of these apples
h1,h2,?,hn, you are required to answer some independent queries. Each query is two integers
p,q, which asks the number of apples Taotao would pick, if the height of the
p-th apple were
q
(instead of
hp). Can you answer all these queries?
【hdu6406 Taotao Picks Apples 多校第8场1010】
Input
The first line of input is a single line of integer
T
(1≤
T≤
10), the number of test cases.
Each test case begins with a line of two integers
n,m
(1≤
n,m≤
105), denoting the number of apples and the number of queries. It is then followed by a single line of
n
integers
h1,h2,?,hn
(1≤
hi≤
109), denoting the heights of the apples. The next
m
lines give the queries. Each of these
m
lines contains two integers
p
(1≤
p≤
n)
and
q
(1≤
q≤
109), as described in the problem statement.
Output
For each query, display the answer in a single line.
Sample Input15 31 2 3 4 41 55 52 3
Sample Output153HintFor 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(){ 7for(int i = 1; i < = n; i ++){ 8dmax[i][0] = a[i]; 9} 10for(int j = 1; (1< < j) < = n; j ++){ 11for(int i = 1; i+(1< < j)-1< = n; i ++){ 12dmax[i][j] = max(dmax[i][j-1],dmax[(1< < (j-1))+i][j-1]); 13} 14} 15 } 16 int getValue(int l, int r){ 17int k = 0; 18while(1< < (k+1) < = (r-l+1))k++; 19return max(dmax[l][k],dmax[r-(1< < k)+1][k]); 20 } 21 int find(int l, int r, int x) { 22int pos = -1; 23while(l < = r) { 24int m = (l+r) > > 1; 25if(getValue(l, m) > x) { 26pos = m; 27r = m-1; 28} else l = m+1; 29} 30return pos; 31 } 32 33 int main() { 34scanf("%d", & t); 35while(t--) { 36scanf("%d%d", & n, & m); 37int mx = 0; 38for(int i = 1; i < = n; i ++) { 39scanf("%d", & a[i]); 40if(mx < a[i]) { 41mx = a[i]; 42dp1[i] = dp1[i-1]+1; 43} else dp1[i] = dp1[i-1]; 44cnt[i] = max(a[i], cnt[i-1]); 45} 46init(); 47int tail = 0, head = 1; 48for(int i = n; i > = 1; i --) { 49while(head < = tail & & que[tail] < = a[i]) tail --; 50que[++tail] = a[i]; 51dp2[i] = (tail- head + 1); 52} 53while(m--) { 54scanf("%d%d", & l, & v); 55int ans = dp1[l-1]; 56if(v > cnt[l-1]) ++ ans; 57v = max(v, cnt[l-1]); 58int pos = find(l+1, n, v); 59if(pos != -1) ans += dp2[pos]; 60printf("%d ",ans); 61} 62} 63return 0; 64 }
推荐阅读
- Multiple dex files define Lcom/google/gson/internal/Streams$AppendableWriter$CurrentWrite;
- android在Service中新建TextView
- Spring Boot @DeleteMapping
- android打包生成apk时自定义文件名版本号。自定义项目字段等等
- 第一篇博客(记录Appium环境搭建)
- Android几种解析XML方式的比较
- appium 环境准备
- HDU暑假多校第八场J-Taotao Picks Apples
- hdu 6406Taotao Picks Apples