# tcirc d088 隔離採礦

https://judge.tcirc.tw/ShowProblem?problemid=d088

* 轉移很明顯就是往前找一個最大的dp[i]且i符合題意（中間有隔離）
* 要找到中間有更高點的轉移點，可以用單調隊列。觀察單調隊列會發現，所有之前被pop掉的點都是可以轉移的地方(不包括目前這個點pop掉的)，如下圖黑線範圍

> 0到x1中間有x1作為高點，x1到x2中間有x2作為高點，而x2到x3中間有x4作為高點
> 但是x1, x2, x3和x3-x4中間就沒有高點了

* 所以我們可以開一個線段樹，預設都為0，在維護單調對列同時把pop掉的dp值update到線段樹，然後目前的dp就是0到單調對列中第一個比他高的位置(二分搜來找)的區間最大值。
* ~~好像不用線段樹xd~~

#include <bits/stdc++.h>
#define pb push_back
#define F first
#define S second
#define rep(X, a,b) for(int X=a;X<b;++X)
#define ALL(a) (a).begin(), (a).end()
#define SZ(a) (int)(a).size()
#define NL "\n"
using namespace std;
typedef pair<long long,long long> pll;
typedef pair<int,int> pii;
typedef long long ll;

int h[1000010], v[1000010];
int dp[1000010]={0}, tree[4000010]={0};

void upd(int v, int l, int r, int pos, ll x){
    if(l==r){
        tree[v]=x;
        return;
    }
    int mid=(l+r)>>1;
    if(pos<=mid) upd(2*v, l, mid, pos, x);
    else upd(2*v+1, mid+1, r, pos, x);
    tree[v]=max(tree[2*v], tree[2*v+1]);
}

ll get(int v, int l, int r, int ql, int qr){
    if(l==ql && r==qr) return tree[v];
    int mid=(l+r)>>1;
    if(qr<=mid) return get(2*v, l, mid, ql, qr);
    else if(ql>mid) return get(2*v+1, mid+1, r, ql, qr);
    else return max(get(2*v, l, mid, ql, mid), get(2*v+1, mid+1, r, mid+1, qr));
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin>>n;
    rep(i,0,n) cin>>h[i];
    rep(i,0,n) cin>>v[i];
    vector<int> stk;
    ll ans=0;
    rep(i,0,n){
        while(!stk.empty() && h[stk.back()]<h[i]){
            upd(1, 0, n-1, stk.back(), dp[stk.back()]);
            stk.pop_back();
        }
        dp[i]=v[i];
        // find the first element greater than h[i], didnt use lowerbound because MLE
        int l=0, r=stk.size(), mid;
        while(l<r-1){
            mid=(l+r)>>1;
            if(h[stk[mid]]<=h[i]) r=mid;
            else l=mid;
        }

        if(!stk.empty()) dp[i]+=get(1, 0, n-1, 0, stk[l]);
        stk.pb(i);
        ans=max(ans, (ll)dp[i]);
    }
    cout<<ans<<NL;
}