转载请注明出处： http://www.cnblogs.com/fraud/ ——by fraud
Trees
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
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?
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)
5
2
3
6
2
2
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.
//#####################
//Author:fraud
//Blog: http://www.cnblogs.com/fraud/
//#####################
#include <iostream>
#include <sstream>
#include <ios>
#include <iomanip>
#include <functional>
#include <algorithm>
#include <vector>
#include <string>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <climits>
#include <cctype>
using namespace std;
#define XINF INT_MAX
#define INF 0x3FFFFFFF
#define MP(X,Y) make_pair(X,Y)
#define PB(X) push_back(X)
#define REP(X,N) for(int X=0;X<N;X++)
#define REP2(X,L,R) for(int X=L;X<=R;X++)
#define DEP(X,R,L) for(int X=R;X>=L;X--)
#define CLR(A,X) memset(A,X,sizeof(A))
#define IT iterator
typedef long long ll;
typedef pair<int,int> PII;
typedef vector<PII> VII;
typedef vector<int> VI;
int Scan()
{
int res, ch=;
while(!(ch>=''&&ch<='')) ch=getchar();
res=ch-'';
while((ch=getchar())>=''&&ch<='')
res=res*+ch-'';
return res;
}
void Out(int a)
{
if(a>)
Out(a/);
putchar(a%+'');
}
int h[];
int q[];
int p[];
int px[];
int ans[];
bool cmp(int x,int y){
if(q[x]==q[y])return x<y;
return q[x]<q[y];
}
bool cmp1(int x,int y){
return h[x]<h[y];
}
int main()
{
//ios::sync_with_stdio(false);
int n,m;
while(scanf("%d%d",&n,&m)!=EOF){
h[n+]=-;h[]=-;
for(int i=;i<=n;i++)h[i]=Scan();
for(int i=;i<=n;i++)px[i]=i;
sort(px+,px+n+,cmp1);
for(int i=;i<=m;i++)q[i]=Scan();
for(int i=;i<=m;i++)p[i]=i;
sort(p+,p+m+,cmp);
int j=;
ans[]=;
p[]=;
for(int i=;i<=m;i++){
ans[p[i]]=ans[p[i-]];
while(j<=n&&h[px[j]]<=q[p[i]]){
h[px[j]]=-;
if(h[px[j]-]==-&&h[px[j]+]==-)ans[p[i]]--;
else if(h[px[j]-]>&&h[px[j]+]>)ans[p[i]]++;
j++;
}
}
for(int i=;i<=m;i++){
printf("%d\n",ans[i]);
}
}
return ;
}