算法1

(暴力) $O(q)$

注意到 $x$ 的范围在 $1 \sim 2 \times 10 ^ 5$ 以内且不重复，因此对于每次入队操作，可以记 $p[x]$ 表示 $x$ 的位置，维护一个假的双端队列即可。

具体地，维护队列的队头下标 hh 和队尾下标 tt，对于三种操作：

• 操作1：让 hh-- 并将 $x$ 插入 hh 的位置，即 p[x] = --hh。
• 操作2：人类的本质是复读机，p[x] = ++tt。
• 操作3：求 $x$ 在队列中的位置到队列两段的最小值，即 min(tt - p[x], p[x] - hh)

时间复杂度 $O(m)$。

C++ 代码

#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 200005;

int m, x;
char str[2];
int p[N], hh, tt = -1;

int main()
{
    scanf("%d", &m);
    while (m--)
    {
        scanf("%s%d", str, &x);
        if (*str == 'L') p[x] = --hh;
        else if (*str == 'R') p[x] = ++tt;
        else printf("%d\n", min(tt - p[x], p[x] - hh));
    }
    return 0;
}

算法2

(倒推) $O(q)$

赛时没想到正着的搞法，于是打算反着来搞。

离线，将所有操作存入一个数组 q，同时维护一个真的双端队列（可以用 STL 啦），俺题意将所有数插入。

将得到的双端队列看成一个序列，倒着处理每次询问的操作。

问题转化为，给一个序列，每次删第一个数或最后一个，查询某个数到边界的最小值。

对于队列中的每个数 x，预处理 l[x] 表示 x 到序列最左端的距离，r[x] 表示 x 到序列最右端的距离。

删第一个数和最后一个数是对称的，以下只考虑删第一个数的情况。

对于从删第一个数的操作，所有 l[x] 都减少 $1$，暴力枚举 $x$ 是肯定不行的。

这里可以记 delta 表示删除第一个数的操作次数，每次删第一个数让 delta ++，那么每次查找 l[x] 变为查 l[x] - delta 即可。

复杂度 $O(q)$。

C++ 代码

#include <cstdio>
#include <cstring>
#include <deque>

using namespace std;

const int N = 200005;

int m, x;
struct Op
{
    char c; int x;
} q[N];
char str[2];

deque<int> dq;
int l[N], r[N], dl, dr;
int res[N], idx;

int main()
{
    scanf("%d", &m);
    for (int i = 1; i <= m; i ++ )
    {
        scanf("%s%d", str, &x);
        q[i] = {*str, x};
        if (q[i].c == 'L') dq.push_front(x);
        else if (q[i].c == 'R') dq.push_back(x);
    }

    for (int i = 0; dq.size(); ++i)
    {
        int x = dq.front();
        dq.pop_front();
        l[x] = i, r[x] = dq.size();
    }

    for (int i = m; i; --i)
        if (q[i].c == 'L') ++dl;
        else if (q[i].c == 'R') ++dr;
        else res[++idx] = min(l[q[i].x] - dl, r[q[i].x] - dr);

    for (int i = idx; i; --i) printf("%d\n", res[i]);

    return 0;
}