POJ 2374

挺水的一道线段树+DP题。可以从底往上添加线段，每添加线段之前查询端点所被覆盖的区间线段。再从最顶往下DP，每次从端点出发，递推覆盖该端点的区间线段的两端的值即可。

 #include <cstdio>
 #include <iostream>
 #include <cstring>
 #include <cctype>
 #include <algorithm>
 #define LL __int64
 using namespace std;  const int N= ;
 const int SN=;
 const int inf=(<<);
 int mark[N*];
 int n,s;
 int dp[SN][];
 struct Seg{
     int l,r;
     int li,ri;
 }seg[SN]; void PushDown(int rt){
     if(mark[rt]!=-){
         mark[rt<<]=mark[rt<<|]=mark[rt];
         mark[rt]=-;
     }
 } void update(int rt,int L,int R,int l,int r,int d){
     if(L<=l&&r<=R){
         mark[rt]=d;
         return ;
     }
     PushDown(rt);
     int m=(l+r)>>;
     if(L<=m)update(rt<<,L,R,l,m,d);
     if(m<R)update(rt<<|,L,R,m+,r,d);
 } int query(int rt,int index,int l,int r){
     if(mark[rt]!=-){
         return mark[rt];
     }
     int m=(l+r)>>;
     if(index<=m) return query(rt<<,index,l,m);
     else return query(rt<<|,index,m+,r);
 } int main(){
     while(scanf("%d%d",&n,&s)!=EOF){
         int mm=N,mc=-N;
         memset(mark,-,sizeof(mark));
         for(int i=n-;i>=;i--){
             scanf("%d%d",&seg[i].l,&seg[i].r);
             mm=min(seg[i].l,mm);
             mc=max(seg[i].r,mc);
             dp[i][]=dp[i][]=inf;
         }
         seg[n].l=mm; seg[n].r=mc;
         mm=abs(mm);
         dp[n][]=dp[n][]=inf;
         mm++;
         update(,,seg[n].r+mm,,mc+mm,n);
         for(int i=n-;i>=;i--){
             seg[i].li=query(,seg[i].l+mm,,mc+mm);
             seg[i].ri=query(,seg[i].r+mm,,mc+mm);
             update(,seg[i].l+mm,seg[i].r+mm,,mm+mc,i);
         }
         dp[][]=abs(seg[].l-s),dp[][]=abs(seg[].r-s);
         int ans=inf;
         int li,ri;
         for(int i=;i<n;i++){
             li=seg[i].li; ri=seg[i].ri;
             if(li==n){
                 ans=min(ans,dp[i][]+abs(seg[i].l-));
             }
             if(ri==n){
                 ans=min(ans,dp[i][]+abs(seg[i].r-));
             }
             dp[li][]=min(dp[li][],dp[i][]+abs(seg[li].l-seg[i].l));
             dp[li][]=min(dp[li][],dp[i][]+abs(seg[li].r-seg[i].l));
             dp[ri][]=min(dp[ri][],dp[i][]+abs(seg[ri].l-seg[i].r));
             dp[ri][]=min(dp[ri][],dp[i][]+abs(seg[ri].r-seg[i].r));
         }
         printf("%d\n",ans);
     }
     return ;
 }