HDU 6534 – Chika and Friendly Pairs

题目链接:HDU 6534

考虑莫队算法,对$a_i$、$a_i + k$、$a_i – k$进行离散化,用树状数组维护一个值域的前缀和。渐进时间复杂度$O(n \times \sqrt{n} \times \log n)$。

这里要注意我们对于每一个$a_i$,要先预处理出$a_i – k$、$a_i$和$a_i + k$离散化之后的值,然后在add和remove操作的时候就可以$O(1)$得到它们离散化之后的结果,否则会TLE。

 

说点什么

avatar
50
  Subscribe  
提醒