Trees

Accepts: 156

Submissions: 533

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

问题描述

今天CodeFamer去坎树。有N 棵树排成一排。他们被从1 到N 标号。第i 号树的高度为h i  。两棵未被坎掉的树编号分别为x,y

当且仅当他们满足如下条件中一条时，他们是属于同一个块的:
1) x+1=y 或 y+1=x;
2) 存在一个棵未被坎掉的树，编号为z ，x 和z 在同一个块并且y 和z 也在同一个块。
现在CodeFamer想要坎掉一些高度不大于某个值的树，坎掉之后会形成多少个块呢？

输入描述

多组测试数据(大概15 组)
对于每一组数据,第一行包含两个整数N 和Q ,以一个空格分开,N 表示有N 棵树,Q 表示有Q 个查询。
在接下来的N 行中,会出现h[1],h[2],h[3],…,h[N] 
,表示N 棵树的高度。
在接下来的Q 行中,会出现q[1],q[2],q[3],…,q[Q] 
表示CodeFamerr查询。

请处理到文件末尾。

[参数约定]
1≤N,Q≤50000 


0≤h[i]≤1000000000(10 9 ) 


0≤q[i]≤1000000000(10 9 )

输出描述

对于每一个q[i]，输出CodeFamer坎掉高度不大于q[i]的树之后有多少个块。

输入样例

输出样例

0
2

Hint

在这个样例中，有3棵树，他们的高度依次是5 2 3。

对于6这个查询，如果CodeFamer坎掉高度不大于6的树，那么剩下的树高度形状是-1 -1 -1（-1表示那个树被坎掉了）。这样就有0个块。

对于2这个查询，如果CodeFamer坎掉高度不大于2的树，那么剩下的树高度形状是5 -1 3（-1表示那个树被坎掉了）。这样就有2个块。

离线处理询问

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<functional>
#include<iostream>
#include<cmath>
#include<cctype>
#include<ctime>
#include<vector>
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define Rep(i,n) for(int i=0;i<n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define RepD(i,n) for(int i=n;i>=0;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define Forpiter(x) for(int &p=iter[x];p;p=next[p])  
#define Lson (x<<1)
#define Rson ((x<<1)+1)
#define MEM(a) memset(a,0,sizeof(a));
#define MEMI(a) memset(a,127,sizeof(a));
#define MEMi(a) memset(a,128,sizeof(a));
#define INF (2139062143)
#define F (100000007)
#define MAXN (50000+10)
#define fi first
#define se second 
typedef long long ll;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return (a-b+(a-b)/F*F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
int n,Q;
ll h[MAXN],q[MAXN];
bool b[MAXN];
pair<ll,int> ask[MAXN],work[MAXN];
int sum[MAXN];
int main()
{
//	freopen("c.in","r",stdin);
	
	while(scanf("%d%d",&n,&Q)==2)
	{
		MEM(h) MEM(q) MEM(b)
		For(i,n)
		{
			scanf("%d",&h[i]);
			work[i]=make_pair(h[i],i); 
			b[i]=1;
		}
		sort(work+1,work+1+n);
		For(i,Q)
		{
			scanf("%d",&q[i]);
			ask[i]=make_pair(q[i],i); 
		} 
		sort(ask+1,ask+1+Q);
		
		int i=1,j=1,ans=1;
		while (j<=Q)
		{
			if (i<=n&&work[i].fi<=ask[j].fi) //cut tree
			{
				int now=work[i].se;
				b[now]=0;
				ans+=b[now-1]+b[now+1]-1;
				i++;
			}
			else // calc ans
			{
				int now=ask[j].se;
				sum[now]=ans;
				j++;
			}
		} 
		For(i,Q) printf("%d\n",sum[i]);
	}
	
	return 0;
}

秒客网

BestCoder Round #36(Trees-离线处理询问)

Trees

相关文章