Yuki 318 学学学学学 ( Ad hoc / Segment Tree )

No.318 学学学学学 - yukicoder

題意：
給一個數列 A。現在要產生另一個數列 B。產生的步驟為：
for each integer t in 1 to 1e9:
__for each integer x in leftmostPositionInA( t ) to rightmostPositionInA( t ):
____B[ x ] = t
求 B 的最終樣貌

資料規模：
數列大小 1≤n≤1e5
1≤a[ i ]≤1e9
時限 2000 ms
記憶體 512 MB

解法：
首先這顯然可以用延遲評價線段樹裸打。但我們利用單調性考慮更簡單的方法：
對於每個新的 B[ i ]，其值為最大的 v，v 為任意值，在 A數列中滿足存在兩個 v 分別在其左端( 含 )和右端( 含 )。
因此可以從左更新到右，利用 set，在 A 中遇到不在 set 裡面的，就是左界，變押入，然後當前的 B[ i ] 便是 set 中的最大值。賦值後，若當前的數字在 A 中為右界，就從 set 中移除。
雖然可以用雙向佇列做優化，但離散化時複雜度已經是 O( N lg N )，所以沒有必要。

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

int N;
vi A;

void init(){
  cin >> N;
  A = vi( N );
  for( int i = 0; i < N; ++i )
    cin >> A[ i ];
}

map< int, int > last_pos;
vi B;

void preprocess(){
  for( int i = 0; i < N; ++i )
    last_pos[ A[ i ] ] = i;
  B = vi( N );
  set< int > covering_a;
  for( int i = 0; i < N; ++i ){
    if( not covering_a.count( A[ i ] ) )
      covering_a.emplace( A[ i ] );
    B[ i ] = *--covering_a.end();
    if( i == last_pos[ A[ i ] ] )
      covering_a.erase( A[ i ] );
  }
}

void solve(){
  for( int i = 0; i < N; ++i )
    cout << B[ i ] << " \n"[ i + 1 == N ];
}