如题，题目在中女中的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