EDPC Q - Flowers

問題のリンク

Q - Flowers

思考過程

・LIS（最長増加部分列）問題の拡張版。重み付きLIS。
・いわゆるインラインDPというやつ。DP table を1次元にして、セグ木にのせる。
・セグ木版LISを重み付きで行う。逆に、LISは全重みが1のFlowersであると言える。
・セグ木にのせるものは、dp[h[i]] := 最後尾の高さがh[i]である花の単調増加列の美しさの総和の最大値。

インラインDP

・DP table をセグ木にのせたもの（だと思ってる。。）。
・区間を利用した遷移を高速にしたいときに使える。
・とてもよくわかる解説↓
LIS でも大活躍！ DP の配列使いまわしテクニックを特集 - Qiita

手続き

1. 区間最大一点更新のセグ木を準備。葉にはdp[x] = 0 がのっているとする。
2. h[i] を座圧。（今回は必要なし）
3. a[i], h[i] を前から見ていき、dp[h[i]]をmax{ dp[j] | 0 <= j < h[i] } + a[i] に更新する。
4. max{ dp[j] | all j } が答え。

以下実装

#include <iostream>
#include <algorithm>
#include <vector>
#include <functional>
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
using namespace std;
template<class T>bool chmax(T &a, const T &b) { if(a < b){ a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if(a > b){ a = b; return 1; } return 0; }
typedef long long ll;
template <typename T>
struct SegTree{
  // 二項演算merge,単位元identify
  using F = function<T(T, T)>;
  T identity;
  F merge; 
  int size;
  vector<T> dat;
  
  // 二項演算fと単位元idを渡して宣言する
  SegTree(F f,T id):merge(f),identity(id){}

  // データの要素の数nを渡して初期化、sizeはnより大きい2の冪乗
  void init(int n){
    size = 1;
    while(size<=n) size *= 2;
    dat.resize(size*2-1,identity);
  }

  // 配列を渡して0(n)で初期化
  void build(vector<T> vec){
    rep(i,vec.size()) dat[size-1+i] = vec[i];
    dfs(0);
  }
  
  T dfs(int k){
    if(k>=size-1) return dat[k];
    else return dat[k] = merge(dfs(2*k+1),dfs(2*k+2));
  }

  // index kの要素をaに変更
  void update(int k,T a){
    k += size - 1;
    dat[k] = a;
    while(k > 0){
      k = (k-1)/2;
      dat[k] = merge(dat[2*k+1],dat[2*k+2]);
    }
  }

  // 区間[a,b)に対するクエリに答える。(k,l,r)=(0,0,size)
  T query(int a,int b,int k,int l,int r){
    if(r<=a||b<=l) return identity;
    
    if(a<=l&&r<=b) return dat[k]; 
    else return merge(query(a,b,2*k+1,l,(l+r)/2),query(a,b,2*k+2,(l+r)/2,r));
  }
  
  void show(){
    int index = 0;
    int num = 1;
    while(index<size){
      rep(i,num){
    if(dat[i+index]==identity) cout << "e ";
    else cout << dat[i+index] << " ";
      }
      cout << "\n";
      num *= 2;
      index = index*2+1;
    }
  }
  
};


ll LIS(vector<int> h, vector<ll> a) {
  int n = h.size();
  
  auto f = [&](ll a, ll b) { return max(a, b); };
  ll id = 0;
  SegTree<ll> seg(f, id);
  seg.init(n);
  ll res = 0;
  rep(i,n) {
    ll x = seg.query(0, h[i], 0, 0, seg.size);
    seg.update(h[i], x+a[i]);
    chmax(res, x+a[i]);
  }
  return res;

}

int main()
{
  int n;cin >> n;
  vector<int> h(n);
  rep(i,n) cin >> h[i];
  vector<ll> a(n);
  rep(i,n) cin >> a[i];

  cout << LIS(h, a) << "\n";
  
  return 0;
}