题名误我青春!
认为这道题不太需要什么算法,只需要一点想象力qaq
思路
我们可以看下题目,可以发现我们的重点是操作三。
因为每个数都不重复,且只能在两边插入,所以我们可以保存好每个数插入时左边($l$)与右边($r$)各插入了多少数。
对于在左边插入的数:
它的右边在一开始有 $l+r$ 个数,左边有 $0$ 个数。所以我们对于此后任意一个对 $x$ 的询问,可以有两种可能:
- 现在的 $l$ 减去当时的 $l$。
- 现在的 $r$ 加上当时的 $l$。
对于右边插入的数:
- 现在的 $r$ 减去当时的 $r$。
- 现在的 $l$ 加上当时的 $r$。
代码:
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int Qread () {
int res = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') { if (ch == '-') f *= -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { res = (res << 1) + (res << 3) + (ch ^ 48); ch = getchar(); }
return res * f;
}
struct Point {
int l, r;
bool jud;
} h[N];
int l, r;
main() {
int T;
T = Qread ();
while (T --) {
char ch = getchar();
while (ch != 'L' && ch != 'R' && ch != '?')
ch = getchar();
int x = Qread();
if (ch == 'L')
h[x] = {++ l, r, 0};
if (ch == 'R')
h[x] = {l, ++ r, 1};
if (ch == '?') {
if (!h[x].jud)
printf ("%d\n", min (l - h[x].l, r + h[x].l - 1));//减一是要减去当时的自己
else
printf ("%d\n", min (r - h[x].r, l + h[x].r - 1));
}
}
}
贴一个python的
瓜瓜
大佬Orz
hxd,你的qread第二个while什么意思啊
快速读入
可以baidu一下,经常用
谢谢·
关于快读比cin还要慢这件事……
(虽然已经知道是数据量小的原因了)
# (但我还是怀恨在心)
# 它让我那道题差点光荣地直接TLE
我感觉我废了 跟 y 总的比起来好长。。。