如題，題目在中女中的OJ上(http://tcgs.tc.edu.tw:1218/ShowProblem?problemid=z033)
目前沒人通過且NPSC補完計畫上的程式碼也是會TLE，當年的紀錄也沒有隊伍AC。
題目的數字個數最多會有 1e6 個，雖然時限是 6s
但枚舉任意組的開頭和結尾形成的子區間判斷會吃TLE。
附個暴力法實作的 Code : https://www.codepile.net/pile/oVxp1RVO
想問一下這題有O(N^2)的暴力法外的其他作法嗎?

https://pastebin.com/2MAAqeQq 用了 merkle tree做到 O(logN) 的時間更新"所有數字奇偶狀態的"的 hash但這應該不是 intended solution... 坐等高手

題目的舉例我看不懂 為什麼吃掉1有算一種？哦 原來數字是種類不是數量用積分方式算［0,L] 的奇偶數， 相扣可以得到任意[L,R]的奇偶數，所以只統計相同奇偶數出現次數k算所有c(k,2)加起來是答案，樓上用 hash tree 加速做掉了？

這是國中題目 所以有國中數學的解法...? 坐等高手+1

就樓上的方法啦, 積分方式其實就是 prefix sum 而已統計可以用例如 std::map 或 std::unordered_map

種類太多 感覺也只能hash了不過hash要怎麼存才不會爆記憶體?

就…只存hash出的值，不存原本的值，祈禱不會碰撞把10^6個數字hash到uint64_t，有碰撞產生的機率差不多是 (10^6)^2 / 2^64 而已 (birthday attack)

剛剛用1e18+3這個prime modulo喇過了...仔細想想 1e6種數字 裝到1e60的buckets 還會碰撞也太賽講錯 1e18的buckets