2015-4-5阅读94 评论0

Trees

Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 65536/65536 K (Java/Others)

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

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

0h[i]1000000000(109)

0q[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

HintIn 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
#include
#include
#include
#include
#include
#include
#include
#define PI acos(-1.0)
#define M 1000005  //10^6
#define eps 1e-8
#define LL long long
#define moo 1000000007
#define INF -999999999
using namespace std;
struct aa
{
int id;
int num;
int ans;
}a[100000];//记录查询的结构体
struct bb
{
int id;
int num;
}b[100000];//记录树高度的结构体
int vis[100000];//记录第i个点的树有没有长出来
bool cmp1(bb x,bb y)
{
return x.num>y.num;
}
bool cmp2(aa x,aa y)
{
return x.num>y.num;
}
bool cmp3(aa x,aa y)
{
return x.id=b[nowb].num)
{
a[nowa].ans=ans;
nowa++;
}//当前查询比下一个长的树高，查询结果即为当前长着的树的分块数
else
{
for(;b[nowb].num>a[nowa].num&&nowb<=n;nowb++)
{
int p=b[nowb].id;
vis[p]=1;
if(vis[p-1]==1&&vis[p+1]==1)
ans--;
else if(vis[p-1]==0&&vis[p+1]==0)
ans++;
}
//将此时所有能长的树都长出来
}
}
//处理一下所有树都长完之后剩余的查询
if(nowb==n+1)
for(;nowa<=m;nowa++)
a[nowa].ans=ans;
//讲查询排回原序并输出
sort(a+1,a+m+1,cmp3);
for(int i=1;i<=m;i++)
printf("%d\n",a[i].ans);
}
return 0;
}


(注：此网站文章大都来自公开的博客，如有原作者发现有侵权问题，请在此留言，我们会立刻删除相关文章。)