首先~感性理解理性分析一下会发现,如果不考虑额外删除的第一个,对全局模拟一次删除,求出每个点的删除时间和是前面哪个点给他删除的,那么在进行区间询问的时候,如果一个点被删除了并且不是被第一个点删除的,那么这个点的删除点和删除时间是不会变的。
现在只需要考虑第一个是怎么删除的。原题解给出的做法是直接模拟这个过程,但是我并没有想到(雾。但是我们重新观察一下可以发现,一个点如果其删除点在区间内并且不是被这个删除点删除的,那么这个点被第一个删除的时间等于原来的删除时间。而同时,如果将删除点和被删除点看成一个左闭右开的区间,那么删除时间就是被当前区间完全包含的最大删除时间 \(+1\)。因此可以线段树上二分出第一个实际删除时间大于 \(k\) 的点,那么这前面的所有点都可以被删除,这后面的所有时间大于 \(k\) 的点都不能被删除,用树状数组维护二维数点即可。
一个 \(\log\),但是只比 A_zjzj 的 FHQ-Treap 快一点点,怎么回事呢?
- Another Problem Range Query 6509another problem range query permutation codeforces another problem range query 288d abc permutation another problem 1858c minimization another problem 1637d inversions another problem yet range query 237g sort partiton another problem 1175g another problem 1073g yet 题解permutation another problem