因为数据范围2e5且不重复,直接桶的思想,存入每个数据所在队列中的下表,不断扩大队列的l,r;
直接加减法即可
样例
输入
8
L 1
R 2
R 3
? 2
L 4
? 1
L 5
? 1
输出
1
1
2
时间复杂度 $O(n)$
参考代码
#include<bits/stdc++.h>
#include<list>
using namespace std;
const int N=1e6+10,M=2e5;
int i,j,k,n,m,l,a[N],b[N];
int main(int qwq,char *z[])
{
char s;
cin>>n;
int l=0,r=1;
while(n--)
{
getchar();
cin>>s>>m;
if(s=='L')
{
b[m]=l;
l--;
}
else if(s=='R')
{
b[m]=r;
r++;
}
else if(s=='?')
cout<<min(b[m]-l,r-b[m])-1<<endl;
}
return 0;
}