USACO2018FEB GOLD Snow Boots

wjh15101051's space

卧薪尝胆，厚积薄发。

Date: Tue Sep 18 22:05:03 CST 2018

In Category: NoCategory

Description：

$n$ 个格子 $m$ 双靴子，每个靴子有能承受的最大积雪深度和最大步长，给出所有格子雪的深度，问哪些靴子可以从 $1$ 走到 $n$ 。

$1\le n \le 100000,1\le m \le 100000$

Solution：

看上去像是一个可达性 $DP$ ，然而 $O(nm)$ 的复杂度是承受不住的，往 $DP$ 上想就走远了，其实看到 $10^5$ 就应该想到 $\log$ 数据结构的。

可以发现只要最长的一段没有能走的格子长度 $\ge d$ ，那么就不合法，于是把所有格子按深度排序，把所有靴子按深度排序，一个个加入，用线段树维护最长的没有格子的长度，即可判断当前靴子能否走到头。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 100010

struct blo{int h,pos;}b[MAXN];

bool blo_cmp_h(blo a,blo b){return a.h < b.h;}

struct bot{int h,d,id;}s[MAXN];

bool bot_cmp_h(bot a,bot b){return a.h < b.h;}

struct node

{

	int lc,rc;

	bool cov;

	int len,llen,rlen,mlen;

	node(){cov = false;}

}t[MAXN << 1];

int ptr = 0;

int newnode(){return ++ptr;}

int root;

#define mid ((l + r) >> 1)

void maintain(int rt)

{

	t[rt].cov = t[t[rt].lc].cov | t[t[rt].rc].cov;

	t[rt].llen = (t[t[rt].lc].cov == false ? t[t[rt].lc].len + t[t[rt].rc].llen : t[t[rt].lc].llen);

	t[rt].rlen = (t[t[rt].rc].cov == false ? t[t[rt].rc].len + t[t[rt].lc].rlen : t[t[rt].rc].rlen);

	t[rt].mlen = max(t[t[rt].lc].rlen + t[t[rt].rc].llen,max(t[t[rt].lc].mlen,t[t[rt].rc].mlen));

	return;

}

void build(int &rt,int l,int r)

{

	rt = newnode();

	t[rt].len = r - l + 1;

	if(l == r)

	{

		t[rt].cov = false;

		t[rt].llen = t[rt].rlen = t[rt].mlen = 1;

		return;

	}

	build(t[rt].lc,l,mid);

	build(t[rt].rc,mid + 1,r);

	maintain(rt);

	return;

}

void insert(int rt,int p,int l,int r)

{

	if(l == r)

	{

		t[rt].llen = t[rt].rlen = t[rt].mlen = 0;

		t[rt].cov = true;

		return;

	}

	if(p <= mid)insert(t[rt].lc,p,l,mid);

	else insert(t[rt].rc,p,mid + 1,r);

	maintain(rt);

	return;

}

int ans[MAXN];

int main()

{

	scanf("%d%d",&n,&m);

	for(int i = 1;i <= n;++i)scanf("%d",&b[i].h);

	for(int i = 1;i <= n;++i)b[i].pos = i;

	for(int i = 1;i <= m;++i)scanf("%d%d",&s[i].h,&s[i].d);

	for(int i = 1;i <= m;++i)s[i].id = i;

	sort(s + 1,s + 1 + m,bot_cmp_h);

	sort(b + 1,b + 1 + n,blo_cmp_h);

	build(root,1,n);

	for(int i = 1,j = 1;i <= m;++i)

	{

		while(j <= n && b[j].h <= s[i].h)

		{

			insert(root,b[j].pos,1,n);

			++j;

		}

		if(t[root].mlen >= s[i].d)ans[s[i].id] = 0;

		else ans[s[i].id] = 1;

	}

	for(int i = 1;i <= m;++i)printf("%d\n",ans[i]);

	return 0;

}

In tag: 数据结构-线段树

wjh15101051