FZU 2236中如何运用离散化与树状数组实现高效计算？

本文共计1260个文字，预计阅读时间需要6分钟。

【简化版】离散化 + 题记：以下为离散化。离散化：当题目数据很大时，但数值个数不多，可以采用离散化，降低数值，便于计算。例如：数列 {89, 14, 9, 1000, 2}；离散化后：{4, 3, 2, 5, 1}；（此处省略）

借此题记一下离散化。离散化：当题目数据很大时，但数的个数不多，可以采用离散化，降低数值，便于计算。

例如数列{ 89, 14, 9, 1000, 2 }；离散化后：{ 4, 3, 2, 5, 1 }；（此操作后，数值整体降低，甚至可以当数组下标使用了）

具体操作参见本题代码。

离散化三部曲：

1. 数组 ha[] 存储所有存在过的数据，sort排序

2. 对ha数组进行去重，重复的数据只保留一个。