IOI 2012 Crayfish Scrivener ( Rope )

PEG Judge - IOI '12 - Crayfish Scrivener

題意：
要求支持三種詢問至多 1e6 筆：
T L: 在當前字串尾添上字符 L
U a: 取消前 a 個操作
P x: 輸出當前第 x 位的字符

解法：
Rope 水過，詳見代碼。

時間 / 空間複雜度：
有人說內部是持久化平衡樹，有人說是分塊結構，但我只知道它很快。

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

const int MAXM = ( int ) 1e6;

rope< char > ver[ MAXM + 1 ];

signed main(){
  ios::sync_with_stdio( 0 );
  int M; cin >> M;
  int f = 0;
  for( int qi = 0; qi < M; ++qi ){
    string op; cin >> op;
    if( op[ 0 ] == 'T' ){
      string L; cin >> L;
      ver[ f + 1 ] = ver[ f ];
      ver[ f + 1 ].push_back( L[ 0 ] );
      ++f;
    } else if( op[ 0 ] == 'U' ){
      int U; cin >> U;
      ver[ f + 1 ] = ver[ f - U ];
      ++f;
    } else if( op[ 0 ] == 'P' ){
      int P; cin >> P;
      cout << ver[ f ][ P ] << "\n";
    }
  }
  return 0;
}