维护一个sum数组，有点划分树的思想，写过划分树的应该能看出来
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
#include<stack>
#include<cmath>
#include<queue>
#include<map>
using namespace std;
const int maxn=;
int sum[maxn<<],is[maxn];
void pushup(int rt)
{
sum[rt]=sum[rt*]+sum[rt*+];
}
void build(int rt,int l,int r)
{
if(l==r)
{
is[l]=sum[rt]=;
return;
}
int m=(l+r)>>;
build(rt*,l,m);
build(rt*+,m+,r);
pushup(rt);
}
void change(int rt,int l,int r,int pos,int c)
{
if(l==r)
{
sum[rt]=c;
return;
}
int m=(l+r)>>;
if(pos<=m)change(rt*,l,m,pos,c);
else change(rt*+,m+,r,pos,c);
pushup(rt);
}
int query(int rt,int l,int r,int k)
{
if(l==r)
{
return l;
}
int m=(l+r)>>;
if(sum[rt*]>=k)return query(rt*,l,m,k);
else return query(rt*+,m+,r,k-sum[rt*]);
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
build(,,n);
for(int i=;i<m;++i)
{
char s[];
int k;
scanf("%s%d",s,&k);
if(s[]=='L')
{
int x=query(,,n,k);
is[x]=;
change(,,n,x,);
}
else if(s[]=='R')
{
if(is[k]==)continue;
is[k]=;
change(,,n,k,);
}
else
{
int x=query(,,n,k);
printf("%d\n",x);
}
}
return ;
}