新高一暑假第一期集训恢复性训练【数据结构-线段树晚测】(补)
新高一暑假第一期集训恢复性训练【数据结构-线段树晚测】(补)
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。