计蒜客41387 – XKC’s basketball team

题目链接:ICPC 2019 徐州赛区网络赛 E

对于每个$a_i$,我们要找一个最大的$j > i$,满足$a_j \geq a_i + m$。

考离线询问。对于一个点$a_i$,加入一个询问和一个修改——在$i$位置插入$a_i$,和一个查询——比$a_i + m$大的最大的$j$。我们可以对修改和查询进行排序,用优先队列维护比当前$a_i + m$大的最大的$j$,然后离线回答即可。

渐进时间复杂度$O(n \log n)$。

 

说点什么

avatar
50
  Subscribe  
提醒