算法
(平衡二分搜索木) $O(Q\log L)$
查询某点 $x$ 所在的那一段的长度,只需找到离它左右最近的切割点即可。
这里的切割点是乱序的,所以需要将它排好序,还要找待查点所在的那一段木材的左右端点,我们可以想到 平衡二分搜索木
刚好可以实现这个需求,并且 C++ 中有 std::set
可以使用。
可以先把 $0$ 和 $L$ 压入,表示 $[0, L)$ 的区间,这样处理起来会比较方便
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::set;
int main() {
int L, q;
cin >> L >> q;
set<int> s;
s.insert(0);
s.insert(L);
rep(qi, q) {
int c, x;
cin >> c >> x;
if (c == 1) {
s.insert(x);
}
else {
auto it = s.lower_bound(x);
int r = *it;
--it;
int l = *it;
int ans = r - l;
cout << ans << '\n';
}
}
return 0;
}