Bangladesh OI 2016 National Round pA. Guess the Queue ( BIT + Deque )

http://codeforces.com/gym/101212/attachments/download/5014/bangladesh-informatics-olympiad-2016-en.pdf
Dashboard - Bangladesh Informatics Olympiad 2016 - Codeforces

題意：
實現一個雙向佇列，可以回答以下三種詢問：
1. ‘1 x y’ ID 為 y 的人從前面( x = 'F' )或後面( x = 'B' )進入
2. ‘2 x’ 前面( x = 'F' )或後面( x = 'B' )的人退出
3. ‘3 x y’ 若 x = 'D' 輸出隊中第 y 前面的人，否則 x = 'P' 輸出 ID 為 y 的人在第幾個位子
並且保證出過隊伍的人不會再進去

資料規模：
For easy version: 1 ≤ N ≤ 2000. [25% of total score]
For hard version: 1 ≤ N ≤ 200000. [100% of total score]
In general,
1 ≤ each ID ≤ 10^9, IDs are unique for each person
1 ≤ each position ≤ current size of the queue
TL: 4000 ms
ML: 256 MB

解法：
如果無視 3.P 的操作，完全就能用雙向佇列水過。現在問題是要如何維護 ID 對應到位子的資料。位子等價前面排多少人，所以考慮給每個人進隊時一個特徵值，可以拿來和其他人比較隊中的前後關係。維護兩個指針，隊首和對尾的特徵值。當一個人進隊的時候，得到相應的特徵值，用 BIT 統計隊中的人的特徵值，便能查詢有多少人特徵值比當前的人小，就相當是當前的人在隊中的位子。

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

const int offset = ( int ) 2e5 + 2;

struct ftree{
  vi dat;
  ftree( int sz ){
    dat = vi( sz );
  }
  void update( int x, int v ){
    for( int i = x; i < dat.size(); i += i & -i ){
      dat[ i ] += v;
    }
  }
  int sum( int x ){
    int res = 0;
    for( int i = x; i > 0; i -= i & -i ){
      res += dat[ i ];
    }
    return res;
  }
};

void solve(){
  int T; cin >> T;
  for( int kase = 1; kase <= T; ++kase ){
    cout << "Case " << kase << ":" << endl;
    int N; cin >> N;
    deque< int > dq;
    map< int, int > id2pos;
    int fptr = offset, bptr = offset;
    ftree *bit = new ftree( offset * 2 );
    for( int n_qry = 0; n_qry < N; ++n_qry ){
      int op; cin >> op;
      string dir; cin >> dir;
      if( op == 1 ){
        int id; cin >> id;
        if( dir == "F" ){
          dq.emplace_front( id );
          id2pos[ id ] = fptr;
          bit->update( fptr, 1 );
          if( fptr == bptr ){
            ++bptr;
          }
          --fptr;
        } else{
          dq.emplace_back( id );
          id2pos[ id ] = bptr;
          bit->update( bptr, 1 );
          if( fptr == bptr ){
            --fptr;
          }
          ++bptr;
        }
      } else if( op == 2 ){
        if( dir == "F" ){
          bit->update( id2pos[ dq.front() ], -1 );
          dq.pop_front();
        } else{
          bit->update( id2pos[ dq.back() ], -1 );
          dq.pop_back();
        }
      } else{
        int id; cin >> id;
        if( dir == "D" ){
          cout << dq[ id - 1 ] << endl;
        } else{
          cout << bit->sum( id2pos[ id ] ) << endl;
        }
      }
    }
  }
}