HDU 5200 Trees

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

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

In the following N lines, there will appear h[1],h[2],h[3],…,h[N]

In the following Q lines, there will appear q[1],q[2],q[3],…,q[Q]

Please process to the end of file.

[Technical Specification]

1≤N,Q≤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

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.

按照高度排個序，從小到大取走這些樹，根據條件判斷剩下的塊數。

然後讀入數字後二分查找其位置，輸出答案即可。

也可以選擇讀入詢問并排序然後在計算塊數時直接記錄答案在按照标号輸出。

#include<stdio.h>
#include<algorithm>
#include<map>
#include<cstdlib>
#include<cstring>
using namespace std;
map<int, int > M;
const int maxn = 50005;
int n, m, x, sum[maxn], f[maxn];
struct abc
{
    int h, id;
    abc(){}
    abc(int h, int id) :h(h), id(id){}
}a[maxn];

bool cmp(const abc&a, const abc&b)
{
    return a.h < b.h;
}

bool operator <(const int &a, const abc &b)
{
    return a< b.h;
}

int main()
{
    while (scanf("%d%d", &n,&m)!=EOF)
    {
        memset(f, 0, sizeof(f));
        memset(sum, 0, sizeof(sum));
        for (int i = 0; i < n; i++)
        {
            scanf("%d", &x);
            a[i] = abc(x, i);
        }
        sort(a, a + n, cmp);
        for (int i = 0; i < n; i++)
        {
            if (i) sum[i] = sum[i - 1]; else sum[i] = 1;
            if (a[i].id - 1 >= 0 && !f[a[i].id - 1] && a[i].id + 1 < n && !f[a[i].id + 1]) sum[i]++;
            if ((a[i].id - 1 < 0 || f[a[i].id - 1]) && (a[i].id + 1 >= n || f[a[i].id + 1])) sum[i]--;
            f[a[i].id] = 1;
        }
        while (m--)
        {
            scanf("%d", &x);
            int k = upper_bound(a, a + n, x) - a;
            if (x < a[k].h) k--;
            if (k>=0) printf("%d\n", sum[k]);
            else printf("1\n");
        }
    }
}