有n个区间自下而上有顺序的排列，标号\(1\sim n\)，第i个区间记做\([l_i,r_i]\)，现在从第n个区间的起点s出发（显然s在\([l_n,r_n]\)内），每次可以选择移动到所在区间的左端点或者右端点，然后跳下去，到达第一个碰到的区间，继续进行相同操作，定义第0个区间为无限延伸，求到第0个区间的位置0的最小水平移动距离，\(n\leq 50000,-1000000\leq l_i,r_i\leq 100000\)。

解

思路一

注意到每个区间到达另一个区间类似图，于是可以通过线段树维护，建出这张图，跑spfa或者dijsktra。

思路二

以区间为状态，设\(f[i][0/1]\)分别表示到达第i个区间左端点和右端点的最小水平移动距离，显然有

\[f[i][0]=\min_{i<j\leq n}\{f[j][0]+l_j-l_i(l_i\leq l_j\leq r_i),f[j][1]+r_j-l_i(l_i\leq r_j\leq r_i)\}\]

\[f[i][1]=\min_{i<j\leq n}\{f[j][0]+r_i-l_j(l_i\leq l_j\leq r_i),f[j][1]+r_i-r_j(l_i\le r_j\leq r_i)\}\]

注意被用过的决策点不能再使用

边界：\(f[n][0]=s-l_n,f[n][1]=r_n-s\)

答案：合法的可以到达此处的决策，具体看代码

于是注意到需要决策点的合法，于是考虑线段树+离散化维护

参考代码：

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #define il inline#define ri register#define Size 50050#define intmax 33686018#define v0 (void)0using namespace std;template
        
         il free Min(free,free);struct lsh{    int a[Size],b[Size],n;    il void prepare(int len,int ar[]){        n=len;for(int i(1);i<=n;++i)a[i]=ar[i];        sort(a+1,a+n+1);for(int i(1);i<=n;++i)b[i]=dfs(ar[i]);    }    il int dfs(int x){        int l(1),mid,r(n);        while(l<=r){            mid=l+r>>1;            if(a[mid]
         
          >1; if(a[mid]>x)r=mid-1; else l=mid+1; }return l; }}L,R;struct segment_tree{ struct DATA{ bool a; int l,r,d; }t[Size<<2]; void build(int p,int l,int r){ t[p].l=l,t[p].r=r,t[p].d=intmax; if(l==r)return;int mid(l+r>>1),pl(p<<1),pr(pl|1); build(pl,l,mid),build(pr,mid+1,r); } il void spread(int p){ if(t[p].a){ int pl(p<<1),pr(pl|1); t[p].a=0,t[pl].a=t[pr].a=1; t[pl].d=t[pr].d=t[p].d; } } void change(int p,int l,int r,int v){ if(l<=t[p].l&&t[p].r<=r)return t[p].a=1,t[p].d=v,v0; spread(p);int mid(t[p].l+t[p].r>>1),pl(p<<1),pr(pl|1); if(l<=mid)change(pl,l,r,v);if(mid
          
           >1),pl(p<<1),pr(pl|1),ans(intmax); spread(p);if(l<=mid)ans=Min(ans,ask(pl,l,r)); if(mid
           
            ='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar(); if(check)x=-x;}template
            
             il free Min(free a,free b){ return a
            
           
          
         
        
       
      
     
    

思路三

注意到思路二枚举了太多了不合法的状态，而且状态被用过还不能再用了，于是考虑倒推，设\(f[i][0/1]\)分别表示从第i个区间到达终点的最短水平移动距离，那么有

\[f[i][0]=\min_{1\leq j<i,l_j\leq l_i\leq r_j}(f[j][0]+l_i-l_j,f[j][1]+r_j-l_i)\]

\[f[i][1]=\min_{1\leq j<i,l_j\leq r_i\leq r_j}(f[j][0]+r_i-l_j,f[j][1]+r_j-r_i)\]

而且每个状态对应的决策点只有一组，于是可以考虑线段树维护每个位置可对应的决策点，而位置范围只有2000000，于是直接暴力建树即可，这样建的树只要一棵。

#include 
    
     #include 
     
      #include 
      
       #define il inline#define ri register#define Size 50050#define v0 (void)0using namespace std;struct segment_tree{    struct DATA{        bool is;        int l,r,d;    }t[800000];    void build(int p,int l,int r){        t[p].l=l,t[p].r=r;if(l==r)return;        int mid(l+r>>1),pl(p<<1),pr(pl|1);        t[p].d=-1,build(pl,l,mid),build(pr,mid+1,r);    }    il void spread(int p){        if(t[p].is){            int pl(p<<1),pr(pl|1);            t[p].is=0,t[pl].is=t[pr].is=1;            t[pl].d=t[pr].d=t[p].d;        }    }    void change(int p,int l,int r,int v){        if(l<=t[p].l&&t[p].r<=r)return t[p].d=v,t[p].is=1,v0;        spread(p);int mid(t[p].l+t[p].r>>1),pl(p<<1),pr(pl|1);        if(l<=mid)change(pl,l,r,v);if(mid
       
        =0)return t[p].d;spread(p);        int mid(t[p].l+t[p].r>>1),pl(p<<1),pr(pl|1);        return mid
        
         il free Abs(free);template
         
          il free Min(free,free);int main(){ int n,s; read(n),read(s),S.build(1,-100000,100000); for(int i(1);i<=n;++i)read(l[i]),read(r[i]); for(int i(1),j;i<=n;++i){ //read(l[i]),read(r[i]); j=S.ask(1,l[i]); if(j)dp[i][0]=Min(dp[j][0]+l[i]-l[j],dp[j][1]+r[j]-l[i]); else dp[i][0]=Abs(l[i]);j=S.ask(1,r[i]); if(j)dp[i][1]=Min(dp[j][0]+r[i]-l[j],dp[j][1]+r[j]-r[i]); else dp[i][1]=Abs(r[i]);S.change(1,l[i],r[i],i); }printf("%d",Min(s-l[n]+dp[n][0],r[n]-s+dp[n][1])); return 0;}template
          
           il free Abs(free x){ return x<0?-x:x;}template
           
            il free Min(free a,free b){ return a
            
             ='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar(); if(check)x=-x;}