第一行，一个整数q,表示操作数
下面q行，每行2个数，表示一个操作
对于每个“？”操作，输出一行一个整数，表示答案
差点暴力上treap
水题一道
因为只有100000个数，所以我们可以维护一个大小为200000的数组以及lll，rrr两个指针
第一个数放在100000这个位置，每次往左放就l--，反之r++
把数填进去，同时写一个映射，将ididid映射为位置
当前位置−l-l−l为左面的数的数量，r−r-r−当前位置为右面的数的数量
然后输出即可
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define rii register int i #define rij register int j using namespace std; int l,r,now,ys[200005]; int q; int main() { scanf("%d\n",&q); for(rii=1;i<=q;i++) { char cz; int id; scanf("%c%d\n",&cz,&id); if(i==1) { ys[id]=100000; l=100000; r=100000; continue; } if(cz==‘L‘) { l--; ys[id]=l; } if(cz==‘R‘) { r++; ys[id]=r; } if(cz==‘?‘) { printf("%d\n",min(ys[id]-l,r-ys[id])); } } }
原文：https://www.cnblogs.com/ztz11/p/9807537.html