「poj 2374」Fence Obstacle Course (线段树+DP)

poj 2374
题意：给你$n$个围栏，对于每个围栏你必须走到其边上才可以往下跳，现在问你从初始最高位置的$n$个围栏，到原点，水平走过的路程最少是多少？

其中$a,b$是这个围栏端点掉下去能掉到的围栏，这个可以用线段树染色维护。
知识点
1、线段树优化 DP 不一定是要维护最优值

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db long double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    const LL MAXN = 200000 + 5, INF = 4223372036854775808ll, BS = 100000;

    LL n, s, x[MAXN], y[MAXN];
    LL dp[MAXN][2];

    LL abss(LL x) {return x > 0 ? x : -x;}

    #define M ((l + r) >> 1)
    #define lc (o << 1)
    #define rc (o << 1 | 1)
    LL col[MAXN * 4];
    void pushdown(LL o, LL len) {
        if (len == 1) return ;
        if (col[o]) {
            col[lc] = col[rc] = col[o];
            col[o] = 0;
        }
    }
    void build(LL o, LL l, LL r) {
        col[o] = 0;
        if (l == r) return ; else {
            build(lc, l, M), build(rc, M + 1, r);
        }
    }
    void update(LL o, LL l, LL r, LL x, LL y, LL v) {
        pushdown(o, r - l + 1);
        if (x <= l && r <= y) {
            col[o] = v;
            return ;
        }
        if (x <= M) update(lc, l, M, x, y, v);
        if (M < y) update(rc, M + 1, r, x, y, v);
    }
    LL query(LL o, LL l, LL r, LL p) {
        pushdown(o, r - l + 1);
        if (l == r) return col[o];
        if (p <= M) return query(lc, l, M, p);
        return query(rc, M + 1, r, p);
    }

    void clean() {
        dp[1][0] = dp[1][1] = 0;
        for (LL i = 2; i <= n; ++i) dp[i][0] = dp[i][1] = INF;
    }
    int solve() {

        clean(); 

        scanf("%lld%lld", &n, &s);
        s += BS;
        build(1, 0, 200000);

        x[0] = y[0] = BS;

        for (LL i = 1; i <= n; ++i) {

            scanf("%lld%lld", &x[i], &y[i]);
            x[i] += BS, y[i] += BS;

            LL a = query(1, 0, 200000, x[i]);
            LL b = query(1, 0, 200000, y[i]);

            dp[i][0] = min(dp[a][0] + abss(x[i] - x[a]), dp[a][1] + abss(x[i] - y[a]));
            dp[i][1] = min(dp[b][0] + abss(y[i] - x[b]), dp[b][1] + abss(y[i] - y[b]));

            update(1, 0, 200000, x[i], y[i], i);

        }

        printf("%lld\n", min(dp[n][0] + abss(s - x[n]), dp[n][1] + abss(s - y[n])));

        return 0;
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}