板子题 P2617。
Difficulty:6.3 / Template
Tag:整体二分
思想就是对答案二分。
把所有答案在区间 [l,r][l,r][l,r] 的询问,修改的值在 [l,r][l,r][l,r] 的操作放一块处理,看看有多少答案在区间 [l,mid][l,mid][l,mid],多少在区间 [mid+1,r][mid+1,r][mid+1,r]。树状数组即可。
还有 std::stable_partition 太好用了你知道吗。
O(nlog2n)O(n\log^2 n)O(nlog2n)。