思路
目前为止应该是最简单的思路。
思路非常简单,由于数据范围很小,只有$2e5$,因此我们只需要开$1e6$的数组大小,然后从中间位置即$5e5$位置开始向两边插入,记录一下每个数出现的位置(只会出现一次,如果多次就会有额外的判断),然后取左边和右边的最小值即可。
比较取巧,建议大家补完题之后学习一下其他常规做法。
时间复杂度为$O(n)$。
代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
using namespace std;
const int N = 1e6;
int l, r;
int p[N];
int g[N];
int main()
{
l = 5e5 + 1, r = 5e5;
int T;
cin >> T;
while (T -- )
{
char op;
int x;
cin >> op >> x;
if (op == 'L')
{
g[ -- l] = x;
p[x] = l;
}
else if (op == 'R')
{
g[ ++ r] = x;
p[x] = r;
}
else
{
cout << min(r - p[x], p[x] - l) << endl;
}
}
return 0;
}