JOI 11 Day4 Bookshelf ( DP + Segment Tree )

Bookshelf(本棚) - joi2011-day4 - 情報オリンピック 問題と解説
bookshelf: 本棚 (Bookshelf) - 2011年 日本情報オリンピック春合宿OJ | AtCoder
「この本を動かすかどうか」を直接決めるのはできなさそう。なのでDPを考えてみる。しかし「今の本を動かす」という状態で転移は難しい。なので逆に「今の本を動かさない」という方向でしてみると、左から右へと順に見て、今の本が最後( 一番右 ) で動かさない本という状態にすると、動かさない本のコストの合計は、その本より左で番号が小さい本のコストの総和と右の本全てのコストの総和だと分かる。これだとDPができる。
結論：こういうDPはまずどう右のものを全てXXとみなしていいかを考えてみるといい。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
const int MAXW = 1e9 + 9;
typedef long long ll;

int n;
int w[ MAXN ];
int a[ MAXN ];

struct itvt{
    ll maxv;
    int lb, rb;
    itvt *lc, *rc;
    itvt(int _l = 0, int _r = 0): maxv(0LL), lb(_l), rb(_r), lc(NULL), rc(NULL){}
    void pull(){
        maxv = max<ll>( lc->maxv, rc->maxv );
    }
    void update(int k, ll v){
        if( lb == rb ){
            maxv = max<ll>( maxv, v );
            return;
        }
        int mid = lb + rb >> 1;
        if( k <= mid ) lc->update( k, v );
        else rc->update( k, v );
        pull();
    }
    ll qmax(int ql, int qr){
        if( qr < lb || rb < ql ) return 0LL;
        if( ql <= lb && rb <= qr ) return maxv;
        ll res = 0LL;
        res = max<ll>( res, lc->qmax( ql, qr ) );
        res = max<ll>( res, rc->qmax( ql, qr ) );
        return res;
    }
};

itvt* buildItvt(int lb, int rb){
    itvt *t = new itvt( lb, rb );
    if( lb == rb ) return t;
    int mid = lb + rb >> 1;
    t->lc = buildItvt( lb, mid );
    t->rc = buildItvt( mid + 1, rb );
    return t;
}

void solve(){
    itvt *root = buildItvt( 1, n );
    ll totsum = 0LL, maxnmv = 0LL;
    for(int i = 1; i <= n; ++i){
        totsum += w[ i ] * 2;
        ll nmv = root->qmax( 1, a[ i ] - 1 ) + w[ a[ i ] ] * 2;
        maxnmv = max<ll>( maxnmv, nmv );
        root->update( a[ i ], nmv );
    }
    printf("%lld\n", totsum - maxnmv);
}

int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i)
        scanf("%d", &w[ i ]);
    for(int i = 1; i <= n; ++i)
        scanf("%d", &a[ i ]);
    solve();
    return 0;
}