tricks I

1.

P2824 排序

碰见这种只有最后有一个查询的问题我们可以考虑二分最后的答案。

具体地，对于当前 \(mid\)，把所有小于 \(mid\) 的设为 \(0\)，其他的设为 \(1\)。此时我们只需要维护最后的位置是否大于 \(mid\) 就好。

那么每次升降序的排序就很好办了。我们用线段树维护一个区间和，也就是这个区间有几个 \(1\)。

升降是一样的，以升序讨论：

令区间长度为 \(l\)，有 \(z\) 个 \(0\)，\(o\) 个 \(1\)。

我们直接把前 \(z\) 个区间赋值为 \(0\)，其他的赋值为 \(1\)。

那么每次二分后我们就知道这个地方是大于等于 \(mid\) 还是小于 \(mid\)。

然后我们就知道答案了。

复杂度：二分是 \(\log n\) 的，每次操作是 \(q\log n\) 的，所以总复杂度是 \(O(q\log^2 n)\)。