JOI 2019 予選 (AOJ 0656) イルミネーション

問題ページ

解法

番目の木までを見たときの美しさの最大値とする。すると遷移は、その木を使わないときとなる。木を使う場合、を満たすに対して高々1本しか木を使えないという制限がある。よって、木を使う場合はこれを満たすものの中で最大のの次に遷移する。これは遅延評価セグ木を用いて管理すればよい。セグ木をが小さい順に更新すれば目的を達成できる。

実装

提出コード - https://onlinejudge.u-aizu.ac.jp/recent_judges/0656/judge/3755513/mhrb_minase/C++14

#include<iostream>
#include<vector>
#include<algorithm>
#include<limits>
using namespace std;

template<typename T>
bool chmax(T &a, T b){
    if(a < b){
        a = b;
        return true;
    }
    return false;
}

template<typename T>
bool chmin(T &a, T b){
    if(b < a){
        a = b;
        return true;
    }
    return false;
}

template<class T>
class SegmentTree{
    int n;
    vector<T> node, upd;
    vector<bool> flag;

    void evaluate(int k, int l, int r){
        if(flag[k]){
            node[k] = upd[k];
            flag[k] = false;
            if(r - l > 1){
                upd[k * 2 + 1] = upd[k];
                flag[k * 2 + 1] = true;
                upd[k * 2 + 2] = upd[k];
                flag[k * 2 + 2] = true;
            }
        }
        return;
    }

    void update(int a, int b, int k, int l, int r, T x){
        evaluate(k, l, r);
        if(b <= l || r <= a){
            return;
        }
        if(a <= l && r <= b){
            upd[k] = x;
            flag[k] = true;
            evaluate(k, l, r);
            return;
        }

        update(a, b, k * 2 + 1, l, (l + r) / 2, x);
        update(a, b, k * 2 + 2, (l + r) / 2, r, x);

        node[k] = max(node[k * 2 + 1], node[k * 2 + 2]);

        return;
    }

    T get(int a, int b, int k, int l, int r){
        evaluate(k, l, r);
        if(b <= l || r <= a){
            return numeric_limits<T>::min();
        }
        if(a <= l && r <= b){
            return node[k];
        }

        T vl = get(a, b, k * 2 + 1, l, (l + r) / 2);
        T vr = get(a, b, k * 2 + 2, (l + r) / 2, r);

        return max(vl, vr);
    }

public:
    SegmentTree(int siz = 0){
        init(siz);
    }

    SegmentTree(const vector<T> v){
        build(v);
    }

    void init(int siz){
        n = 1;
        while(n < siz){
            n <<= 1;
        }

        node.resize(n * 2 - 1);
        fill(node.begin(), node.end(), T(0));

        upd.resize(n * 2 - 1);

        flag.resize(n * 2 - 1);
        fill(flag.begin(), flag.end(), false);

        return;
    }

    void build(const vector<T> v){
        init((int)v.size());

        for(int i = 0, i_len = (int)v.size() ; i < i_len ; ++i){
            node[i + n - 1] = v[i];
        }

        for(int i = n - 2 ; i >= 0 ; --i){
            node[i] = max(node[i * 2 + 1], node[i * 2 + 2]);
        }

        return;
    }

    void update(int a, int b, T x){
        update(a, b, 0, 0, n, x);
        return;
    }

    T get(int a, int b){
        return get(a, b, 0, 0, n);
    }
};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    int n, m;
    cin >> n >> m;

    vector<long long> a(n);
    for(int i = 0 ; i < n ; ++i){
        cin >> a[i];
    }

    vector<int> l(m), r(m), id(m);
    for(int i = 0 ; i < m ; ++i){
        cin >> l[i] >> r[i];
        --l[i];
        --r[i];
        id[i] = i;
    }

    sort(id.begin(), id.end(), [&](int i, int j){ return r[i] < r[j]; });

    SegmentTree<int> seg(n);
    for(int i = 0 ; i < n ; ++i){
        seg.update(i, i + 1, i + 1);
    }

    for(int i = 0 ; i < m ; ++i){
        seg.update(l[id[i]], r[id[i]] + 1, r[id[i]] + 1);
    }

    vector<long long> dp(n + 1);
    for(int i = 0 ; i < n ; ++i){
        chmax(dp[i + 1], dp[i]);
        chmax(dp[seg.get(i, i + 1)], dp[i] + a[i]);
    }

    cout << dp[n] << endl;

    return 0;
}