→ sifmelcara: 做到 O(logN) 的時間更新"所有數字奇偶狀態的"的 hash 04/21 11:09
→ sifmelcara: 但這應該不是 intended solution... 坐等高手 04/21 11:10
→ longlongint: 題目的舉例我看不懂 為什麼吃掉1有算一種？ 04/21 12:19
→ longlongint: 哦 原來數字是種類不是數量 04/21 12:20
推 longlongint: 用積分方式算［0,L] 的奇偶數， 相扣可以得到任意[L, 04/21 13:39
→ longlongint: R]的奇偶數，所以只統計相同奇偶數出現次數k算所有c( 04/21 13:39
→ longlongint: k,2)加起來是答案，樓上用 hash tree 加速做掉了？ 04/21 13:39
推 GYLin: 這是國中題目 所以有國中數學的解法...? 坐等高手+1 04/21 23:46
推 LPH66: 就樓上的方法啦, 積分方式其實就是 prefix sum 而已 04/22 00:56
→ LPH66: 統計可以用例如 std::map 或 std::unordered_map 04/22 00:56
推 GYLin: 種類太多 感覺也只能hash了 04/22 02:33
推 GYLin: 不過hash要怎麼存才不會爆記憶體? 04/22 02:41
→ sifmelcara: 就…只存hash出的值，不存原本的值，祈禱不會碰撞 04/22 10:41
→ sifmelcara: 把10^6個數字hash到uint64_t，有碰撞產生的機率差不 04/22 10:43
→ sifmelcara: 多是 (10^6)^2 / 2^64 而已 (birthday attack) 04/22 10:44
推 GYLin: 剛剛用1e18+3這個prime modulo喇過了... 04/22 14:08
→ GYLin: 仔細想想 1e6種數字 裝到1e60的buckets 還會碰撞也太賽 04/22 14:09
→ GYLin: 講錯 1e18的buckets 04/22 14:10