111qqz的小窝

老年咸鱼冲锋!

poj 2299 Ultra-QuickSort (树状数组+离散化)

这道题可以总结的地方不少。

1:对于一组乱序数列,每次只能交换相邻元素,达到有序交换的次数就是原数列中你逆序对的个数。
  cf上好像总喜欢出这个题。。。我印象中就出现三次了。。。。。
2:原始数组a[i]和树状数组的t[i]的对应问题(???存在疑问。。。应该只是这道题,而不是一般规律!)
  这道题n是500000,如果直接开数组是可以开得下的,不需要离散化。但是树状数组的下标对应的是原始数组的值!也就是t[i]的下表最大可能为999,999,999 ! 显然存不下,需要离散化。
3:学习了离散化的又一种写法。

 

说点什么

您将是第一位评论人!

提醒
wpDiscuz
粤ICP备18103363