Books Queries
题意
有一个序列，初始为空。
有 \(q\) 次询问，每次询问为以下三种操作中的一种：
L x，一个大写字母L，和一个编号x，表示将x放入序列最左边。R x，一个大写字母R，和一个编号x，表示将x放入序列最右边。? x，一个问号?，和一个编号x，询问x距离序列最左端或者最右端的距离最小值，每行输出一个答案
保证 x 在询问时已经在序列中，保证 x 不会重复放入序列。
数据范围
- \(1 \leqslant q,x \leqslant 2 \times 10^5\)
思路
这题其实绕一点点思路。
这里只是问它距离序列最左端和最右端的距离的最小值，并不要求整个序列，所以只需要记录一下每个 x、队头还有队尾对应着哪个数值即可。
注意，为了不出现队列中有空的部分导致的答案出错的问题，队尾对应的数值应该初始化为-1
复杂度
- 时间：\(O(q)\)
- 空间：\(O(x)\)
Code
点击查看代码
#include <iostream>
using namespace std;
const int N = 2e5 + 10;
int t_, x, a[N], h, t = -1; // 初始化细节
char c;
int main(){
ios::sync_with_stdio(0), cin.tie(0);
for (cin >> t_; t_; t_--) {
cin >> c >> x;
if (c == 'L') {
a[x] = --h; // 记录对应数值
} else if (c == 'R') {
a[x] = ++t;
} else {
cout << min(t - a[x], a[x] - h) << '\n'; // O(1) 处理询问！
}
}
return 0;
}