题解 P4269 【[USACO18FEB]Snow Boots G】
- 除了链表和并查集，还有线段树的方法。
-
对于靴子
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;
}