Super Mario 2 solution

#include<bits/stdc++.h>
#define int long long
using namespace std;

class segtree {
private:
    vector<int> a,t; int n;
    void build(int l, int r, int node){ //O(n)
        int mid = (l + r) / 2;
        if (l == r)
            t[node] = a[l];
        else {
            build(l, mid, node * 2+1);
            build(mid + 1, r, node * 2 + 2);
            t[node] = min(t[node * 2 + 1], t[node * 2 + 2]);
        }
    }
    int rmq(int l, int r, int i, int j, int node) {
        int mid = (l + r) / 2;
        if (i <= l && j >= r) return t[node];
        if (j < l || r < i) return 1e17;
        int p1 = rmq(l, mid, i, j, node * 2 + 1);
        int p2 = rmq(mid + 1, r, i, j, node * 2 + 2);
        return min(p1, p2);
    }
    void update(int l, int r, int idx, int val, int node) {
        int mid = (l + r) / 2;
        if (idx < l || r < idx)
            return;
        else if (l == r)
            t[node] = val;
        else {
            update(l, mid, idx, val, node * 2 + 1);
            update(mid + 1, r, idx,val, node * 2 + 2);
            t[node] = min(t[node * 2 + 1], t[node * 2 + 2]);
        }
    }
    
public:
    segtree(int n, vector<int>& arr) {
        this->n = n;
        t.resize(4 * n), a.resize(n);
        for (int i = 0; i < n; ++i) a[i] = arr[i];
        build(0, n - 1, 0);
    }
    void update(int idx, int val) { update(0, n - 1, idx, val, 0); }
    int rmq(int l, int r) { return rmq(0, n - 1, l, r, 0); }
};

int32_t main() {
    int n; cin >> n;
    vector<int> a(n + 1), c(n + 1), dp(n + 1, 1e17);
    for(int i = 1; i <= n;++i) cin >> c[i];
    for(int i = 1; i <= n;++i) cin >> a[i];
    dp[n] = 0;
    segtree tree(n + 1, dp);
    for(int i = n - 1; i >= 1; --i)
        dp[i] = tree.rmq(i + 1, a[i]) + c[i], tree.update(i, dp[i]);
    cout << dp[1];
}