Books Queries [Codeforces Round #515 (Div. 3) C]

http://codeforces.com/contest/1066/problem/C

以下のクエリを処理せよ。
L id := キューの左端にidを追加する
R id := キューの右端にidを追加する
? id := キューの中のidのmin(左から何番目, 右から何番目)を出力する

解法

http://codeforces.com/contest/1066/submission/44195680

クエリ先読みで解く。
最終的に作られるキューをdequeを使って再現しよう。
そこから、rev配列を作る。
rev[i] := idがiである要素はキューの左から何番目
これを使って、?クエリを答えていこう。
　
L := キューに入れられている添字の左端
R := キューに入れられている添字の右端
すると、idの左から何番目にあるかはL - rev[id]となる。
同様に右から何番目にあるかはrev[id] - Rとなる。

int Q; char T[201010]; int id[201010];
int rev[201010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> Q;
    deque<int> dq;
    rep(q, 0, Q) {
        cin >> T[q] >> id[q];
        if (T[q] == 'L') dq.push_front(id[q]);
        else if (T[q] == 'R') dq.push_back(id[q]);
    }

    int i = 0;
    while (!dq.empty()) {
        int q = dq.front(); dq.pop_front();
        rev[q] = i;
        i++;
    }

    int l = inf, r = -inf;
    rep(q, 0, Q) {
        if (T[q] == '?') {
            int c = rev[id[q]];

            int ans = min(c - l, r - c);
            printf("%d\n", ans);
        } else {
            chmin(l, rev[id[q]]);
            chmax(r, rev[id[q]]);
        }
    }
}