HDU - 5200 - Trees (upper_bound)

Trees
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 205    Accepted Submission(s): 68
Problem Description
Today CodeFamer is going to cut trees.There are 
N  trees standing in a line. They are numbered from 
1  to 
N . The tree numbered 
i  has height 
hi . We say that two uncutted trees whose numbers are 
x  and 
y  are in the same block if and only if they are fitting in one of blow rules:
1)x+1=y or y+1=x;
2)there exists an uncutted tree which is numbered 
z , and 
x  is in the same block with 
z , while 
y  is also in the same block with 
z .
Now CodeFamer want to cut some trees whose height is not larger than some value, after those trees are cut, how many tree blocks are there?
 
Input
Multi test cases (about 
15 ).
For each case, first line contains two integers 
N  and 
Q  separated by exactly one space, N indicates there are 
N  trees, 
Q  indicates there are 
Q  queries.
In the following 
N  lines, there will appear 
h[1],h[2],h[3],…,h[N]  which indicates the height of the trees.
In the following 
Q  lines, there will appear 
q[1],q[2],q[3],…,q[Q]  which indicates CodeFamer’s queries.
Please process to the end of file.
[Technical Specification]
1 \leq N, Q \leq 50000
0≤h[i]≤1000000000(109)
0≤q[i]≤1000000000(109)
 
Output
For each 
q[i] , output the number of tree block after CodeFamer cut the trees whose height are not larger than 
q[i] .
 
Sample Input

   
   
   
   

    
    
    
    3 2
5
2
3
6
2
   
   
   
   

 
Sample Output

   
   
   
   

    
    
    
    0
2


    
    
    
    
 
     
 
      Hint 
     
In this test case, there are 3 trees whose heights are 5 2 3. For the query 6, if CodeFamer cuts the tree whose height is not large than 6, the height form of left trees are -1 -1 -1(-1 means this tree was cut). Thus there is 0 block. For the query 2, if CodeFamer cuts the tree whose height is not large than 2, the height form of left trees are 5 -1 3(-1 means this tree was cut). Thus there are 2 blocks. 
    
    
    
    
     
   
   
   
   

 
Source
BestCoder Round #36 ($)
 
STLの二分検索関数には3つのlower_があります.bound 、upper_bound 、binary_search .この3つの関数はいずれも秩序区間(もちろんこれも二分検索を用いる前提)に用いられ,以下にこの2つの関数を記録する.
ForwardIter lower_bound(ForwardIter first,ForwardIter last,const_Tp&val)アルゴリズムは、値val以上の最初の非減算シーケンス[first,last]の位置を返す.
ForwardIter upper_bound(ForwardIter first,ForwardIter last,const_Tp&val)アルゴリズムは、非減算シーケンス[first,last]の最初の値valより大きい位置を返します.
ACコード:

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

const int maxn = 100005;
int n, q;
int h[maxn], ans[maxn], vis[maxn];
pair<int, int> p[maxn];

int main() {
	while(scanf("%d %d", &n, &q) != EOF) {
		for(int i = 1; i <= n; i++) {
			scanf("%d", h + i);
			p[i] = make_pair(-h[i], i);
		}
		
		memset(vis, 0, sizeof(vis));
		
		sort(p + 1, p + n + 1);//       ，          
		
		int sum = 0;//          
		for(int i = 1; i <= n; i++) {
			int x = p[i].second;
			if(!vis[x - 1] && !vis[x + 1]) sum ++;//    ，          
			else if(vis[x - 1] && vis[x + 1]) sum --;//        ，           ，                 
			ans[i] = sum;//      i     （        ）         
			vis[x] = 1;
		}
		
		for(int i = 0; i < q; i++) {
			int t;
			scanf("%d", &t);//upper_bound         [first, last)        val   。 
			int id = upper_bound(p + 1, p + n + 1, 	make_pair(-t, -1)) - p - 1;
			printf("%d
", ans[id]);
		}
	}
	return 0;
}