dp+线段树，dp是核心，线段树用来优化复杂度，dp过程好像，但是要确定从一个fence边缘向下沿直线走，下一个fence是哪个，最朴素的想法就是从上到下扫描，时间为O(n2)，数据量比较大，可能会超时。然后用线段树来优化这个过程，当输入第i个fence的左右点时，1~i-1的fence所覆盖区间已插入到了线段树中（并在所覆盖的区间发记录fence编号）那么此时，求fence(i)的左点l向下会走到哪个fence，可以从线段树的根开始搜索，搜索到l的这条路径上的最大编号，也就是覆盖了点l的区间上的最大编号，从而得到所求编号
#include <iostream>
#include <cstdio>
#include <cmath>
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
using namespace std;
const int maxm=(100000+10)*3;
const int maxn=50000+10;
int num[maxm*3];
int n,s,ul,ur,ql,qr;
int f[maxn][2],rloc,next[maxn][2],setv,seg[maxn][2];
void Update(int no,int l,int r)
{
if(l>=ul&&r<=ur)
{
if(setv>num[no]) num[no]=setv;
return;
}
int mid=l+(r-l)/2;
if(ul<=mid) Update(no*2+1,l,mid);
if(ur>mid) Update(no*2+2,mid+1,r);
}
void Query(int no,int l,int r)
{
if(l>=ql&&r<=qr)
{
rloc=max(rloc,num[no]);
return;
}
int mid=l+(r-l)/2;
if(ql<=mid) Query(no*2+1,l,mid);
if(qr>mid) Query(no*2+2,mid+1,r);
rloc=max(rloc,num[no]);
}
int main()
{
scanf("%d%d",&n,&s);
int i;
memset(num,0,sizeof(num));//初始化线段树
for(i=1;i<=n;i++)
{
scanf("%d%d",&ul,&ur);
seg[i][0]=ul;seg[i][1]=ur;
rloc=-1;ql=qr=ul;
Query(0,-100000,100000);
next[i][0]=rloc;
rloc=-1;ql=qr=ur;
Query(0,-100000,100000);
next[i][1]=rloc;
setv=i;
Update(0,-100000,100000);
}
f[0][0]=f[0][1]=0;
seg[0][0]=seg[0][1]=0;
for(i=1;i<=n;i++)//dp过程
{
int j1=next[i][0],j2=next[i][1];
f[i][0]=min((f[j1][0]+abs(seg[i][0]-seg[j1][0])),(f[j1][1]+abs(seg[i][0]-seg[j1][1])));
f[i][1]=min(f[j2][0]+abs(seg[i][1]-seg[j2][0]),f[j2][1]+abs(seg[i][1]-seg[j2][1]));
}
int ans=min(f[n][0]+abs(s-seg[n][0]),f[n][1]+abs(s-seg[n][1]));
printf("%d\n",ans);
return 0;
}