新高一暑假第一期集训恢复性训练【数据结构-线段树晚测】(补)

新高一暑假第一期集训恢复性训练【数据结构-线段树晚测】(补)

A. [CF1045G] AI robots

我们先按视野降序排序，这样一个一个考虑，如果后面的能看到前面，那前面的也肯定能看到后面。

这样，就是对于每一个机器人，在他前面有几个智商在 \([q-k,q+k]\)，位置在 \([x-r,x+r]\)。

那么把这个东西看做一个矩形覆盖就可以了。

然后因为智商这一维维数很小，我们可以对每一个智商开一个动态开点线段树，然后一个一个扫过去统计答案就可以了。

B. [CF1000F] One Occurrence

先把询问离线。

设 \(i\) 位置的数上次出现的位置是 \(p_i\)（如果第一次出现那就是 \(0\)）。

可以想到，用线段树维护一个区间的 \(p\) 的最小值，如果它小于区间左端点，那这个数就是一个合法的答案。

但直接这样做是错的。

考虑 \(1,2,3,4,[1,1],5\)，虽然前一个 \(1\) 的 \(p\) 在区间外面，但他后面还有一个 \(1\)。

所以可以按照询问的右端点排序，推着来维护这个最小值。

具体来说，对于 \(i\)，先把 \(i\) 位置的值改成 \(p_i\)，然后如果有 \(p_i\)，那把 \(p_i\) 位置的值改成 \(+ \infty\)（一开始都要初始化成 \(+ \infty\)） 。

然后再询问的话，查到的就都是这个区间里的最后一次出现的那个数了，就不会GG。