Codeforces Gym 101234A – Hacker Cups and Balls

题目链接:Gym – 101234A

题目来源:2016-2017 National Taiwan University World Final Team Selection Contest

二分答案,每次check的时候建线段树,把比当前答案小的点记为0,比当前答案大的点记为1,那么这个区间的顺序排序就是把所有的0扔到区间的前面,所有的1扔到区间的后面,逆序相反。我们已知$[l,r]$,只需要知道区间当中0的个数或者1的个数就可以通过区间覆盖操作来完成排序。做完$m$个区间覆盖的操作后,查询中间的数,如果中间的数为0,则说明答案在左半区间,否则在右半区间。时间复杂度$O((m+n) \log^2 n)$ 。

 

 

1
说点什么

avatar
50
1 Comment threads
0 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
0 Comment authors
Recent comment authors
  Subscribe  
最新 最旧 得票最多
提醒
trackback

[…] 类似问题:Gym 101234A 题解 […]