【原题题面】传送门
【简化题意】
给定一个长度为n的序列。 有m次询问，每次询问给定两个数si,di。你一开始站在0，每次你可以走不超过di，但你到达的位置的数不能超过si。问能否走到n+1。 n,m<=100000。
【未讲之前】不知道这题哪里跟线段树挂钩了，感觉跟线段树八竿子打不着的关系23333。
【题解】先根据s[i]的限制确定出哪些地方是不能走的，然后按s[i]从小到大排序，维护n上不能走的最长连续长度，因为每一次s[i]越来越大，那么限制越来越小。
还有弄清楚只要最长连续不能走的长度小于相应的d[i]就一定能走。这是因为每次能走的长度是1~d[i]，所以我可以通过一定的调整使每次面临的都是最长连续长度的困难。
【讲了之后】按照s[i]排序离线这一点没想到哇。还有就是这题的切入口不是怎么线段树，而是理解题意之后想怎么维护不能走的最长连续长度，然后才想到可以用线段树。看网上还有题解说可以用set的，也可以实现的吧。
【具体实现】维护最长连续的长度，需要维护当前结点的范围内最长连续不能走的长度sz。
更新这个值需要max,lmax,rmax;
【code】
#include<bits/stdc++.h>
using namespace std; inline int read()
{
int N=,C=;char tf=getchar();
for(;!isdigit(tf);tf=getchar())C|=tf=='-';
for(;isdigit(tf);tf=getchar())N=(N<<)+(N<<)+(tf^);
return C?-N:N;
} const int N=;
int n,q,ans[N];
struct nc
{
int i,s,d;//id step deep
friend bool operator <(nc a,nc b){return a.d==b.d?a.s<b.s:a.d<b.d;}//先放砖
nc(int i=,int s=,int d=):i(i),s(s),d(d){}
}a[N<<];
struct tf
{
int m,l,r,s;//max lmax rmax size
}t[N<<]; void B(int l,int r,int p)
{
t[p].m=t[p].l=t[p].r=t[p].s=r-l+;
if(l==r)return;
int m=l+r>>;
B(l,m,p<<),B(m+,r,p<<|);
} void U(int l,int r,int p,int x)
{
if(l==r){t[p].m=t[p].l=t[p].r=;return;}
int m=l+r>>;x<=m?U(l,m,p<<,x):U(m+,r,p<<|,x); t[p].l=t[p<<].l==t[p<<].s?t[p<<].s+t[p<<|].l:t[p<<].l;
t[p].r=t[p<<|].r==t[p<<|].s?t[p<<|].s+t[p<<].r:t[p<<|].r; t[p].m=max(t[p<<].m,t[p<<|].m);
t[p].m=max(t[p].m,t[p<<].r+t[p<<|].l);
} int main()
{
n=read(),q=read(),B(,n,);
for(int i=,d;i<=n;++i)d=read(),a[i]=nc(i,,d);
for(int i=,d,s;i<=q;++i)s=read(),d=read(),a[i+n]=nc(i,d,s);
sort(a+,a+n+q+); for(int i=;i<=n+q;++i)
{
if(!a[i].s)U(,n,,a[i].i);
else ans[a[i].i]=t[].m<a[i].s;
}
for(int i=;i<=q;++i)printf("%d\n",ans[i]); return ;
}
我的代码不知怎么就是调不出来#￥%……&*），上面是豆哥的。