Dimension travel [ACPC2017 Day1 D]

http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=ACPC2017Day1&pid=D

前提知識

• (自分の解法では)遅延セグメントツリー(区間min更新と区間min)
• (想定解っぽいのは)ダイクストラ

解説

http://judge.u-aizu.ac.jp/onlinejudge/creview.jsp?rid=2536748&cid=ACPC2017Day1

遅延セグメントツリーを活用しながら解く。
使うセグメントツリーは区間min更新（小さい方で更新）と区間min。
st[i] := i次元にいる時のダメージの最小値

魔法をb[i]が小さい方から順に使うか考えていく。
a[i]からジャンプできるダメージの最小値はst[a[i],N]である。
ここから魔法を使うことでb[i]に移動できるが、[0,b[i]]の範囲に移動できるため、この範囲にst[a[i],N]+d[b[i]]をmin更新する。
答えはst[t]である。

template<class V, int NV> struct LazySegTree { // [L,R)
    vector<V> dat, lazy; LazySegTree() { dat.resize(NV * 2, def); lazy.resize(NV * 2, ldef); }
    void update(int a, int b, V v, int k, int l, int r) { push(k, l, r); if (r <= a || b <= l) return;
        if (a <= l && r <= b) { setLazy(k, v); push(k, l, r); } else {
        update(a, b, v, k * 2 + 1, l, (l + r) / 2); update(a, b, v, k * 2 + 2, (l + r) / 2, r);
        dat[k] = comp(dat[k * 2 + 1], dat[k * 2 + 2]);}}
    V get(int a, int b, int k, int l, int r) { push(k, l, r); if (r <= a || b <= l) return def;
        if (a <= l && r <= b) return dat[k]; auto x = get(a, b, k * 2 + 1, l, (l + r) / 2);
        auto y = get(a, b, k * 2 + 2, (l + r) / 2, r); return comp(x, y);}
    void update(int a, int b, V v) { update(a, b, v, 0, 0, NV); }
    V get(int a, int b) { return get(a, b, 0, 0, NV); }
    // ---- Template ---------------------------------------------------------------------------------
    // 区間min代入,区間min
    #define INF INT_MAX/2
    const V def = INF, ldef = INF;
    V comp(V l, V r) { return min(l, r); }
    void setLazy(int i, V v) { lazy[i] = min(lazy[i], v); }
    void push(int k, int l, int r) {
        if (lazy[k] != ldef) {
            // modify------------------------------
            dat[k] = min(dat[k], lazy[k]);
            // ------------------------------------
            if (r - l > 1) { setLazy(k * 2 + 1, lazy[k]); setLazy(k * 2 + 2, lazy[k]); }
            lazy[k] = ldef;
        }
    }
};




int N, M, S, T, D[101010];
vector<pair<int,int>> v;
LazySegTree<int, 1 << 17> st;
//--------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M >> S >> T;
    S--; T--;
    rep(i, 0, N) cin >> D[i];
    rep(i, 0, M) {
        int a, b; cin >> a >> b;
        a--; b--;
        v.push_back({a, b});
    }
    sort(v.begin(), v.end(), [&](pair<int, int> a, pair<int, int> b) {
        if (a.second != b.second) return a.second < b.second;
        else return a.first < a.first;
    });
 
    st.update(0, S + 1, 0);
    fore(p, v) {
        int L = p.first;
        int R = p.second;
        //printf("%d %d\n", L, R);
        int c = st.get(L, N) + D[R];
        st.update(0, R + 1, c);
    }
 
    int ans = st.get(T, T + 1);
    cout << ans << endl;
}