LOJ 2055 – 「TJOI / HEOI2016」排序

题目链接:LOJ 2055

类似问题:Gym 101234A 题解

答案的区间是$[1,n]$,考虑二分答案。

在check的时候我们把当前假设的答案记为$u$,比$u$大的位置记为$1$,否则记为$0$,得到一个新的01序列,用这个序列建线段树,维护区间和。当我们遇到对一个区间顺序排序的询问,就是把区间里的1放到区间的最后,否则把0放在区间最后。每次check需要做$m$个操作,操作结束之后如果目标位置的值为$1$,就说明答案大于$u$,否则小于等于$u$。

渐进时间复杂度$O((n + m) \log ^2 n )$。

 

说点什么

avatar
50
  Subscribe  
提醒