题目概述

有 $n$ 个点和 $m$ 个传送点 $(l,r)$ 表示可以从 $l$ 传送到 $r$ ，只能往下爬或者传送。问从 $x$ 出发在不超过 $y$ 且不低于 $x$ 的前提下能够达到的最大的位置。

解题报告

有 $y$ 的限制十分诡异，要想办法去掉，所以考虑离线，按照右端点的顺序加入传送点，这样就不需要考虑 $y$ 了。

然后就是这么个问题：有一个数组 $f_i$ 表示从 $i$ 出发但不能走到 $i$ 以下能够达到的最大位置，然后每个传送实际上就是让 $f_i\ge l$ 的 $f_i$ 与 $r$ 取 $max$ 。

这个可以用线段树科技：记录最大值和严格次小值，对于一个节点，如果最大值大于等于 $l$ 但次小值小于 $l$ 的话就修改该节点并记录tag，tag合并的话分类讨论之后可以分析出来：$(x_1,y_1)+(x_2,y_2)\to(x_1,y_2)$ 。

复杂度我分析不来……求大佬指点。

示例程序

#include<cstdio>
#include<algorithm>
#include<vector>
#define fr first
#define sc second
#define mp make_pair
using namespace std;
const int maxn=100000,maxq=100000;

int n,m,Q,Ls[maxn+5],ans[maxq+5];vector< pair<int,int> > q[maxn+5];
int MAX[(maxn<<2)+5],lst[(maxn<<2)+5],TA[(maxn<<2)+5],TB[(maxn<<2)+5];

inline void Fix(int p,int x) {if (x>MAX[p]) lst[p]=MAX[p],MAX[p]=x; else if (x<MAX[p]&&x>lst[p]) lst[p]=x;}
inline void Pushup(int p) {MAX[p]=-2e9;Fix(p,MAX[p<<1]);Fix(p,lst[p<<1]);Fix(p,MAX[p<<1|1]);Fix(p,lst[p<<1|1]);}
void Build(int l,int r,int p=1){
    if (l==r) {MAX[p]=l;lst[p]=-2e9;return;}int mid=l+(r-l>>1);
    Build(l,mid,p<<1);Build(mid+1,r,p<<1|1);Pushup(p);
}
inline void Addtag(int p,int A,int B) {if (MAX[p]>=A) {MAX[p]=B;if (!TA[p]) TA[p]=A;TB[p]=B;}}
inline void Pushdown(int p) {if (TA[p]) Addtag(p<<1,TA[p],TB[p]),Addtag(p<<1|1,TA[p],TB[p]),TA[p]=TB[p]=0;}
void Insert(int L,int R,int A,int B,int l=1,int r=n,int p=1){
    if (MAX[p]<A) return;if (L==l&&r==R&&lst[p]<A) return Addtag(p,A,B);int mid=l+(r-l>>1);Pushdown(p);
    if (R<=mid) Insert(L,R,A,B,l,mid,p<<1); else if (L>mid) Insert(L,R,A,B,mid+1,r,p<<1|1);
    else Insert(L,mid,A,B,l,mid,p<<1),Insert(mid+1,R,A,B,mid+1,r,p<<1|1);Pushup(p);
}
int Ask(int pos,int l=1,int r=n,int p=1){
    if (l==r) return MAX[p];int mid=l+(r-l>>1);Pushdown(p);
    if (pos<=mid) return Ask(pos,l,mid,p<<1);return Ask(pos,mid+1,r,p<<1|1);
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d%d",&n,&m);for (int i=1,x,y;i<=m;i++) scanf("%d%d",&x,&y),Ls[y]=x;
    scanf("%d",&Q);for (int i=1,x,y;i<=Q;i++) scanf("%d%d",&x,&y),q[y].push_back(mp(x,i));
    for (int i=(Build(1,n),1);i<=n;i++){if (Ls[i]) Insert(1,Ls[i],Ls[i],i);
        for (int si=q[i].size(),j=0;j<si;j++) ans[q[i][j].sc]=Ask(q[i][j].fr);
    }for (int i=1;i<=Q;i++) printf("%d\n",ans[i]);return 0;
}