CTU Open Contest 2019 G. Beer Mugs 异或维护奇偶性

显然的条件:必须L-R中 字符个数最多一个是奇数,其他必须是偶数 由于奇偶性可以用异或表示,区间L,R的奇偶性等于区间1,R异或区间1-(L-1)。 所以 这是个经典的解法:枚举以R为区间右端点,先求出1-R中间的字符数量的奇偶关系。 然后让所有字符全偶,且最左边的位置id,与ans取max。 然后枚举每个字符,令这个字符是奇数,其他是偶数即查询状态(tp ^ (1<<j) )的最早出现的位置。 比赛的时候想的是前缀和维护,虽然是一样的思路但写了80行,导致没调出来。。。 #include using namespace std; typedef long long ll; #d