CSAcademy 25. Min Ends Subsequence ( Persistent Segment Tree )

Round #25 (Div. 2 only)

題意：
給一個排列 1 ~ N，問最長的一個子序列，滿足：頭尾元素都比所有中間的元素大。輸出長度。

制約：
1 ≤ N ≤ 1e5

解法：
不失一般性，假設最長的這個子序列的頭 i 和尾 j 滿足：i < j and A[ i ] ≤ A[ j ]。
枚舉所有 i，令 j 為 i < j and A[ i ] ≤ A[ j ] 中的最大 j。
顯然這個 j 是最優的，而且這對用頭尾下標描述的最長子序列長度是 2 + sum( A[ k ] < A[ i ] for all i < k < j )。
尋找 j 可以用一顆線段樹解決，也就是優先看右半的區間是否可行，不行才往左半。
計算 sum( A[ k ] < A[ i ] for all i < k < j ) 這部分可以用持久化線段樹，詳見代碼。
不過貌似這題標準解法是基於均攤的線性解，好像 50 行左右而已。

時間 / 空間複雜度：
O( N lg N )

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

const int MAXN = ( int ) 1e5;

int N;
int A[ MAXN ];

struct pst{
  static pst mem_pool[ ( int ) 5e6 ];
  int cnt;
  pst *lc, *rc;
  pst(){
    cnt = 0;
    lc = rc = NULL;
  }
  void pull(){
    cnt = ( lc ? lc->cnt : 0 ) + ( rc ? rc->cnt : 0 );
  }
} *root[ MAXN + 1 ], pst::mem_pool[ ( int ) 5e6 ], *mem_ptr = pst::mem_pool;

pst* clone( pst *t ){
  pst *res = new ( mem_ptr++ ) pst();
  res->lc = t->lc;
  res->rc = t->rc;
  res->cnt = t->cnt;
  return res;
}

pst* update( pst *t, int lb, int rb, int k, int v ){
  pst *res;
  if( t ) res = clone( t );
  else res = new ( mem_ptr++ ) pst();
  if( lb + 1 == rb ){
    res->cnt += v;
    return res;
  }
  int mid = lb + rb >> 1;
  if( k < mid ) res->lc = update( res->lc, lb, mid, k, v );
  else res->rc = update( res->rc, mid, rb, k, v );
  res->pull();
  return res;
}

int maxv[ MAXN << 3 ];

void build( int t, int lb, int rb ) {
  if( lb + 1 == rb ) {
    maxv[ t ] = A[ lb ];
    return;
  }
  int mid = lb + rb >> 1;
  build( t << 1, lb, mid );
  build( t << 1 | 1, mid, rb );
  maxv[ t ] = max( maxv[ t << 1 ], maxv[ t << 1 | 1 ] );
}

int qlp( int t, int lb, int rb, int ql, int qr, int v ) {
  if( qr <= lb or rb <= ql ) return N;
  if( lb + 1 == rb ){
    assert( A[ lb ] >= v );
    return lb;
  }
  int mid = lb + rb >> 1;
  if( maxv[ t << 1 ] >= v ) return qlp( t << 1, lb, mid, ql, qr, v );
  else if( maxv[ t << 1 | 1 ] >= v ) return qlp( t << 1 | 1, mid, rb, ql, qr, v );
  return N;
}

int qrp( int t, int lb, int rb, int ql, int qr, int v ) {
  if( qr <= lb or rb <= ql ) return -1;
  if( lb + 1 == rb ){
    assert( A[ lb ] >= v );
    return lb;
  }
  int mid = lb + rb >> 1;
  if( maxv[ t << 1 | 1 ] >= v ) return qrp( t << 1 | 1, mid, rb, ql, qr, v );
  else if( maxv[ t << 1 ] >= v ) return qrp( t << 1, lb, mid, ql, qr, v );
  return N;
}

int gcnt( pst *t ) {
  return t ? t->cnt : 0;
}

int dfs( pst *tl, pst *tr, int lb, int rb, int v ) {
  if( v <= lb ) return 0;
  if( rb <= v ) return gcnt( tr ) - gcnt( tl );
  int mid = lb + rb >> 1;
  return dfs( tl ? tl->lc : NULL, tr ? tr->lc : NULL, lb, mid, v ) + dfs( tl ? tl->rc : NULL, tr ? tr->rc : NULL, mid, rb, v );
}

signed main() {
  ios::sync_with_stdio( 0 );
  cin >> N;
  for( int i = 0; i < N; ++i ) {
    cin >> A[ i ];
    --A[ i ];
    root[ i + 1 ] = update( root[ i ], 0, MAXN, A[ i ], 1 );
  }
  build( 1, 0, N );
  int ans = 1;
  for( int i = 0; i < N; ++i ) {
    int rr = qrp( 1, 0, N, i + 1, N, A[ i ] );
    if( not ( i < rr ) ) continue;
    ans = max( ans, 2 + dfs( root[ i + 1 ], root[ rr ], 0, MAXN, A[ i ] ) );
  }
  for( int i = N - 1; i >= 0; --i ) {
    int ll = qlp( 1, 0, N, 0, i, A[ i ] );
    if( not ( ll < i ) ) continue;
    ans = max( ans, 2 + dfs( root[ ll + 1 ], root[ i ], 0, MAXN, A[ i ] ) );
  }
  cout << ans << endl;
  return 0;
}