围栏障碍训练场

农夫约翰为他的奶牛们建造了一个围栏障碍训练场，以供奶牛们玩耍。

训练场由 N 个不同长度的围栏组成，每个围栏都与 x 轴平行，并且第 i 个围栏的 y 坐标为 i。

训练场的出口位于原点，起点位于 (S,N)
+-S-+-+-+ (fence #N)

+-+-+-+ (fence #N-1)

 ...               ...

+-+-+-+ (fence #2)

 +-+-+-+        (fence #1)

=|=|=|=*=|=|=| (barn)

-3-2-1 0 1 2 3
这些牛会从起点处开始向下走，当它们碰到围栏时会选择沿着围栏向左或向右走，走到围栏端点时继续往下走，按照此种走法一直走到出口为止。

请问，这些牛从开始到结束，行走的水平距离最少为多少。

输入格式
第一行包含两个整数 N 和 S。

第 2..N+1 行，每行包含两个整数 Ai,Bi，表示一个围栏的起始横坐标和结束横坐标，其中第 i+1 行表示第 i 个围栏的数据。

起点坐标满足 AN≤S≤BN。

输出格式
输出一个整数，表示最小水平行走距离。

数据范围
1≤N≤30000,
−105≤S≤105,
−105≤Ai,Bi≤105
输入样例：
4 0
-2 1
-1 2
-3 0
-2 1
输出样例：
4

思路：
算是比较明显的dpdp，小牛每次碰到一个围栏只有两种选择，第一个是向左走，第二个是向右走。

所以我们设f(i,0/1)f(i,0/1)表示在第ii个障碍，小牛碰到当前障碍向左走或者向右走到终点的答案。

那么答案显然是min(f(n,0)+abs(l(n)−s),f(n,1)+abs(r(n)−s))min(f(n,0)+abs(l(n)−s),f(n,1)+abs(r(n)−s))。

那么转移方程呢？假设说我现在在第ii个障碍上，我需要找到我往下走第一个碰到的围栏jj的情况来更新ii的答案。

如何快速找到下面的围栏？

我们需要快速的确定端点和以前的线段的交点，同时更新本次的左右端点的覆盖。

线段树区间修改+单点查询可以快速完成。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 3e4+10;
const int base = 1e5+1;
const int m = base*2;
int n, s;
int l[maxn], r[maxn];
ll f[maxn][2];

struct SegmentTree
{
    int l, r;
    int id;
    int laz;
    #define lson (p<<1)
    #define rson (p<<1|1)
    #define l(x) tree[x].l
    #define r(x) tree[x].r
    #define id(x) tree[x].id
    #define laz(x) tree[x].laz
}tree[m<<2];

void spread(int p)
{
    if(laz(p))
    {
        laz(lson) = laz(rson) = 1;
        id(lson) = id(rson) = id(p);
        laz(p) = 0;
    }
}

void build(int p, int l, int r)
{
    l(p) = l, r(p) = r;
    if(l == r) return;
    int mid = (l+r)>>1;
    build(lson, l, mid); build(rson, mid+1, r);
}

int ask(int p, int x)
{
    if(l(p) == r(p)) return id(p);
    int mid = (l(p)+r(p))>>1;
    spread(p);
    if(x <= mid) return ask(lson, x);
    else return ask(rson, x);
}

void change(int p, int L, int R, int v)
{
    if(L <= l(p) && r(p) <= R) {
        id(p) = v;
        laz(p) = 1;
        return;
    }
    spread(p);
    int mid = (l(p)+r(p))>>1;
    if(L <= mid) change(lson, L, R, v);
    if(mid < R) change(rson, L, R, v);
}

int main()
{
    scanf("%d%d", &n, &s);
    s += base;
    build(1, 1, m);
    //直接走回原点
    l[0] = r[0] = base;
    for(int i = 1; i <= n; i++)
    {
        scanf("%d%d", &l[i], &r[i]);
        l[i] += base; r[i] += base;
        int lv = ask(1, l[i]);
        int rv = ask(1, r[i]);
        f[i][0] = min(f[lv][0]+abs(l[lv]-l[i]), f[lv][1]+abs(r[lv]-l[i]));
        f[i][1] = min(f[rv][0]+abs(l[rv]-r[i]), f[rv][1]+abs(r[rv]-r[i]));
        change(1, l[i], r[i], i);
    }

    int ans = min(f[n][0]+abs(l[n]-s), f[n][1]+abs(r[n]-s));
    cout << ans << endl;
    return 0;