自动搬运

查看原文

来自洛谷，原作者为

	攀岩高手 **

搬运于2025-08-24 21:58:22，当前版本为作者最后更新于2018-09-08 20:45:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

• 除了链表和并查集，还有线段树的方法。

• 对于靴子 $i$ ，我们将它能走的地砖的权值设为 $0$，不能走的地砖的权值设为 $1$ ，并使用线段树维护区间最长的连续的 $1$ 的长度，也就是最长连续的不能走的那段地砖的数量。如果这个值小于靴子 $i$ 的步长，那么答案为 $1$；否则靴子 $i$ 一定无法跨过这段地砖，所以答案为 $0$ 。

• 然而每次枚举一只靴子并在线段树上修改的时间复杂度是 $O(NlogN)$ 的，显然不能过。考虑先将线段树赋为全 $1$ （都不能走），把地砖和靴子按照雪的深度排序，从小到大开始扫描。如果扫到地砖，则在线段树中把这块地砖的位置改为 $0$ （因为以后扫到的靴子能承受的积雪深度都不小于这块地砖的积雪深度，也就是都能走这块地砖）；如果扫到靴子，就统计最长连续的不能走的那段地砖的数量，计算答案。

• 线段树单点修改是 $O(logN)$ 的，查询最长连续 $1$ 的时间复杂度则是 $O(1)$。总时间复杂度：$O(NlogN+B)$。

• 附：线段树维护最长连续 $1$ 的方法：

• 每个结点维护四个值：当前节点维护的区间长度 $len$ ，当前区间最长连续 $1$ 的长度 $maxx$ ，当先区间从左端点开始的最长连续 $1$ 的长度 $maxl$，当先区间从右端点开始的最长连续 $1$ 的长度 $maxr$。

• 那么，当前节点的 $maxl$ 就应该等于它左儿子的 $maxl$ ；如果左儿子的 $maxx$ 等于左儿子维护的区间的长度，就表示左儿子维护的区间全是 $1$ ，那么当前节点 $maxl$ 就应该等于左儿子维护的区间的长度加上右儿子的 $maxl$ 。$maxr$ 的维护方式类似。

• 当前结点的 $maxx$ 则等于它左儿子的 $maxx$ ，右儿子的 $maxx$ ，以及左儿子的 $maxr$ 和 右儿子的 $maxl$ 之和（表示跨越左儿子和右儿子维护的两个区间）这三者的最大值。

• 具体实现见 $pushup$ 函数的代码。

代码实现（c++）：

#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN=110000;
struct SegmentTree
{
	#define lc (root<<1)
	#define rc (root<<1|1)
	struct Node
	{
		bool val;
		int len, maxx, maxl, maxr;
	} tr[MAXN*4];
	void pushup(int root) // 维护区间信息
	{
		tr[root].len=tr[lc].len+tr[rc].len;
		tr[root].maxx=tr[root].maxl=tr[root].maxr=tr[root].val;
		tr[root].maxl=max(tr[root].maxl, tr[lc].maxl);
		if (tr[lc].maxx==tr[lc].len)
			tr[root].maxl=max(tr[root].maxl, tr[lc].len+tr[rc].maxl);
		tr[root].maxr=max(tr[root].maxr, tr[rc].maxr);
		if (tr[rc].maxx==tr[rc].len)
			tr[root].maxr=max(tr[root].maxr, tr[rc].len+tr[lc].maxr);
		tr[root].maxx=max(tr[root].maxx, tr[lc].maxx);
		tr[root].maxx=max(tr[root].maxx, tr[rc].maxx);
		tr[root].maxx=max(tr[root].maxx, tr[lc].maxr+tr[rc].maxl);
	}
	void update(int root, int l, int r, int x) // 单点修改
	{
		if (l==r)
		{
			tr[root].maxx=tr[root].maxl=tr[root].maxr=tr[root].val=0;
			return;
		}
		int mid=l+r>>1;
		if (x<=mid) update(lc, l, mid, x);
		else update(rc, mid+1, r, x);
		pushup(root);
	}
	int query() // 查询
	{
		return tr[1].maxx; // 1 就是树根结点，维护了整个区间
	}
	void build(int root, int l, int r)
	{
		tr[root].val=0;
		if (l==r)
		{
			tr[root].len=1;
			tr[root].maxx=tr[root].maxl=tr[root].maxr=tr[root].val=1;
			return;
		}
		int mid=l+r>>1;
		build(lc, l, mid);
		build(rc, mid+1, r);
		pushup(root);
	}
	#undef lc
	#undef rc
} st;
struct Snow // 这里定义了一个结构体用来排序时记录下标
{
	int id, step, dep;
	bool operator < (const Snow& rhs) const
	{
		return dep!=rhs.dep?dep<rhs.dep:step<rhs.step;
	}
	Snow(int i=0, int s=0, int d=0):
		id(i), step(s), dep(d) {}
} a[MAXN*2];
int n, m;
bool ans[MAXN];
int main()
{
	freopen("snowboots.in", "r", stdin);
	freopen("snowboots.out", "w", stdout);
	scanf("%d%d", &n, &m);
	for (int i=1, f; i<=n; i++)
	{
		scanf("%d", &f);
		a[i]=Snow(i, 0, f);
	}
	for (int i=1, s, d; i<=m; i++)
	{
		scanf("%d%d", &s, &d);
		a[i+n]=Snow(i, d, s);
	}
	sort(a+1, a+n+m+1);
	st.build(1, 1, n);
	for (int i=1; i<=n+m; i++)
	{
		if (a[i].step==0) st.update(1, 1, n, a[i].id);
		else ans[a[i].id]=st.query()<a[i].step;
	}
	for (int i=1; i<=m; i++) printf("%d\n", ans[i]);
	return 0;
}