[USACO18FEB]Snow Boots G

题目链接：[USACO18FEB]Snow Boots G

---

由于询问具有单调性，所以我们可以想到离线来做。

把能走的点当成0，不能走的点当成1，如果最长连续1大于当前最多能走的步数就不合法。

所以我们可以用线段树维护，或者并查集维护。

---

AC代码：

#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=1e5+10;
int n,m,res[N];
struct node{int id,f;}a[N];
struct seg{int ls,rs,s;}t[N<<2],c;
struct query{int id,s,d;}q[N];
#define mid (l+r>>1)
inline seg merge(seg a,seg b,int l1,int l2){
	if(a.ls==l1)	c.ls=a.s+b.ls;
	else	c.ls=a.ls;
	if(b.rs==l2)	c.rs=b.s+a.rs;
	else	c.rs=b.rs;
	c.s=max(max(a.s,b.s),a.rs+b.ls);
	return c;
}
void build(int p,int l,int r){
	if(l==r){t[p].ls=t[p].rs=t[p].s=1; return ;}
	build(p<<1,l,mid),build(p<<1|1,mid+1,r);
	t[p]=merge(t[p<<1],t[p<<1|1],mid-l+1,r-mid);
}
void change(int p,int l,int r,int x){
	if(l==r){t[p].ls=t[p].rs=t[p].s=0; return ;}
	if(x<=mid)	change(p<<1,l,mid,x);
	else	change(p<<1|1,mid+1,r,x);
	t[p]=merge(t[p<<1],t[p<<1|1],mid-l+1,r-mid);
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)	scanf("%d",&a[i].f),a[i].id=i;
	for(int i=1;i<=m;i++)	scanf("%d %d",&q[i].s,&q[i].d),q[i].id=i;
	sort(a+1,a+1+n,[](node a,node b){
		return a.f<b.f;
	});
	sort(q+1,q+1+m,[](query a,query b){
		return a.s<b.s;
	});
	int pos=1;	build(1,1,n);
	for(int i=1;i<=m;i++){
		while(pos<=n&&a[pos].f<=q[i].s)	change(1,1,n,a[pos].id),pos++;
		if(t[1].s<q[i].d)	res[q[i].id]=1;
	}
	for(int i=1;i<=m;i++)	printf("%d\n",res[i]);
	return 0;
}