[USACO2018FEB]Snow Boots G
wangyitong
2018-09-20 17:51:32
[题面传送门](https://www.luogu.org/problemnew/show/P4269)
作为一名noip省一都拿不到的蒟蒻，当然肯定先想暴力：
复杂度O(N*B) :
枚举每一个靴子，再扫一遍雪地，看看不能走的块（我们这里把它称作黑块）最长连续有多长，如果小于等于当前靴子的最大长度，那么当然是可以过去了。
然后好像有优化？
因为我们靴子之间是没有制约关系的，我们可以把靴子从大到小排序，因为这样的话，前一个靴子不能走的块，后面一个靴子也不能走，这样就会使得黑块的数量是单调上升的。
所以我们这样就O(N)扫一遍雪地就行了，但是雪地是无序的，处理起来还是很麻烦，因为被扫过的块有可能能使第i个靴子过，但不能使第$i+1$个靴子过，我们就得再扫一遍雪地。复杂度又爆炸了。
例如：
$hi$=10,$h_{i+1}$=11;
$si$=10,$s_{i+1}$=9;
扫到$si$时我们扫过hi不标黑，扫到$h_{i+1}$把这个块代表的位置标黑了。
然后我们扫$s_{i+1}$时，只能到$h_{i+2}$个雪地了。而对于$s_{i+1}$这个靴子来说，hi也应该是黑的，但我们无法再扫到$hi$了，所以对于这个$s_{i+1}$个靴子来说黑格子多了一个.
所以我们要把靴子和雪地都从大到小排序,然后从大到小枚举靴子和雪地即可.
然后这个时候我们还需要一个链表，我们把n个雪地搞成一个链表，初始每个雪地有一个左指针和右指针，分别指向左边第一个和右边第一个。
然后每次当h[j]>s[i]时，我们就把它在链表中所在的那个位置删除。
但怎么删除呢？
如果我们把当前元素的左指针的右指针指向当前元素的右指针，并且把当前元素的右指针的左指针指向当元素的左指针，那么我们是不是就相当于在链表中跳过了这个元素，就实现了删除操作。
然后统计答案就是链表中所有存在元素的（右指针－左指针）取max即可。
```cpp
// luogu-judger-enable-o2
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<queue>
#include<set>
#define N 120000
#define ri register int
using namespace std;
template <class T> void in(T &x) {
x=0;
bool flag=0;
char c=getchar();
while(c<'0'||c>'9') {
if(c=='-')
flag=1;
c=getchar();
}
while(c>='0'&&c<='9') {
x=(x<<3)+(x<<1)+(c^48);
c=getchar();
}
if(flag)
x=-x;
}
int l[N],r[N];
int h[N],n,m,vis[N],ans[N],maxm=-1;
struct node {
int s,step,id;
} a[N];
struct snow {
int h,id;
} sn[N];
inline bool cmp(node x,node y) {
return x.s>y.s;
}
inline bool cmpp(snow x,snow y) {
return x.h>y.h;
}
int main() {
in(n),in(m);
for(ri i=1; i<=n; ++i)in(sn[i].h),sn[i].id=i;
for(ri i=1; i<=m; ++i)in(a[i].s),in(a[i].step),a[i].id=i;
sort(sn+1,sn+n+1,cmpp);
sort(a+1,a+m+1,cmp);
for(ri i=1; i<=n; ++i)
l[i]=i-1,r[i]=i+1;
int j=1;
for(ri i=1; i<=m; ++i) {
while(j<=n&&sn[j].h>a[i].s) {
r[l[sn[j].id]]=r[sn[j].id];
l[r[sn[j].id]]=l[sn[j].id];
// printf("%d %d %d\n",j,l[j],r[j]);
maxm=max(maxm,(r[sn[j].id]-l[sn[j].id]));
++j;
}
ans[a[i].id]=(a[i].step>=maxm);
}
for(ri i=1; i<=m; ++i)
printf("%d\n",ans[i]);
}
```