题目描述

双端队列支持三种操作，左插右插和查询某个元素要成为队头或者队尾至少需要弹出多少元素。

样例

输入样例1：
8
L 1
R 2
R 3
? 2
L 4
? 1
L 5
? 1
输出样例1：
1
1
2

一种简单的做法

开始想的是直接用list，这样的话插入是O(1),但是查询就比较惨了。然后注意到题目只要求相对位置，那么一个简单的想法是把 x 映射到自身在双端队列里的位置，这里队头初始从 0 开始，左插就队头往负数走，右插就队尾往正数走，查询就直接调出 x 的位置，然后与队头队尾做个差取小即可。上述操作都是 O(1) 的。

C++ 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 3e5;

int Deque[N],ftid,edid;//front index , end index

int main(){
    int q,x;
    char op[2];
    scanf("%d",&q);
    while(q--){
        scanf("%s%d",&op,&x);
        if(op[0] == 'L'){
            Deque[x] = --ftid;
        }else if(op[0] == 'R'){
            Deque[x] = edid++;
        }else{
            int index = Deque[x];
            cout<<min(index-ftid,edid-1-index)<<endl;
        }
    }
    return 0;
}