CodeForces

Luogu

分析

可以用平衡树做,但太麻烦。

其实暴力模拟就好了。

用两个指针L、R维护左右端点,然后用一个数组映射$id->index$即可。

细节见代码。

代码

#include <bits/stdc++.h>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
    return X*w;
}

int a[200010],pos[200010];

int main() {
    re int Q=read(),L=100001,R=100000;
    while (Q--) {
        char c=getchar(); int id=read();
        if (c=='L') a[--L]=id,pos[id]=L;
        else if (c=='R') a[++R]=id,pos[id]=R;
        else if (c=='?') {
            re int p=pos[id];
            printf("%d\n",min(R-p,p-L));
        }
    }
    return 0;
}
最后修改:2019 年 05 月 28 日 08 : 42 PM