CSAcademy 25. Min Ends Subsequence ( Persistent Segment Tree )
題意:
給一個排列 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; }