※ 引述《fatcat8127 (胖胖猫)》之铭言：
: 如题，题目在中女中的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)的暴力法外的其他作法吗?
先讲一下如果数字范围<64的话要怎么做:
假设数字只有K种
那我就能用 K bits 表示"目前各种数字总数之奇偶性"
比方说看完1 1 3 2 3, 共有三种数字,
那他们的数量(2,1,2)奇偶性就是 0 1 0
假设 state[i] 为加入第i个数字时的奇偶性, 共有三种数字
那 state[0] = 000
而区间 [i,j] 是一个符合题目要求的区间
等于是 state[i-1] 跟 state[j] 每个bit要完全一样
以区间尾巴j的角度来看
要数有几个满足的区间头, 就等于是数跟state[j]同样的家伙出现了几次
因为数字最多只有64种, 所以奇偶状态可以用long long表达,
要做到上面的事情, 只要用一个 map<long long, int> 做为各奇偶状态的counter就好
总而言之,
每加入一个Ai -> 更新奇偶状态 ->
将答案加上"以目前位置为尾巴的区间数量" -> counter++
但到目前为止都不是困难的事
此题的数字种类为1e6种, 根本不可能去存各奇偶状态的counter,
于是仔细想想, 奇偶状态虽然总可能性有 2^(1e6) 种,
跑完阵列却也只会出现 1e6种而已,
所以拿个够大的数字%掉, 不要运气太差的话就会过了= =
https://paste.ofcode.org/vnnTrh5q4sW2BfZRv2mWTU