题目大意
有一个N个数的数组A, 如果区间
[l, r]
满足所有数字只出现偶数次, 那么这个区间很好。
问有多少个很好的区间? [latex]N \leq 3 \times 10^5[/latex]
解题报告
基础思想: 乱搞+分块
首先我们发现一个区间的异或和异或区间内所有出现过的数等于0, 那么这个区间就是好区间。
但是前提是数字不能出现
x^y == z
并且xyz都在A内的情况。
于是我们给每个数字随机分配一个64位的标识码拿来异或, 这样冲突概率就很低了。
然后我们从左向右区间右端点i, 问题就变成了区间异或以及区间查询0的数量。
设
lst[x]
为x最后一次出现的位置, 那么每次把
[1, lst[A[i]]]
异或上
A[i]
然后答案累加[1, i]中0的数量即可。
然后这个东西用分块就可以维护了。
代码
用int哈希的…然后被狂暴卡了一波…暂时这样吧…
#include <cstdio> #include <cstring> #include <cstdlib> #include <climits> #include <algorithm> #include <map> #include <set> #include <cmath> using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef unsigned int UI; const int MAXN = 201000; int A[MAXN]; UI rd[1000100]; const int HASHSIZE = (1<<17); const int HASHMASK = (1<<17)-1; struct HashMap { UI code[HASHSIZE]; int val[HASHSIZE]; inline UI hash (UI a) { return (a<<17)^(a<<1)^(a>>7)^(a>>13);}; inline int locate (register UI val) { val = hash(val)+1; register int pos = val&HASHMASK; while(code[pos] != val && code[pos] != 0) { pos = (pos+1)&HASHMASK; } return pos; } void add (UI pos, int v) { register int p = locate(pos); if(code[p] == 0) code[p] = hash(pos)+1LL, val[p] = 0; val[p] += v; } int access (UI pos) { return val[locate(pos)]; } } blocks[500]; UI code[500]; int lst[1000100]; int blocksz; UI suf[MAXN]; void intervalXor (int r, UI val) { register int i, j; for(i = 0, j = 1; i+blocksz<=r; i+=blocksz, j++) code[j] ^= val; //整块异或 for(i = i+1; i<=r; i++) { //暴力修改 blocks[j].add(suf[i], -1); blocks[j].add(suf[i]^val, 1); suf[i]^=val; } } int query (int r, int bid) { //printf("q:[%d, %d, %d]\n", r, bid, blocksz); register int ret = 0; for(register int i = 1; i<bid; i++) ret += blocks[i].access(code[i]); for(register int i = (bid-1)*blocksz+1; i<=r; i++) ret += (code[bid] == suf[i]); return ret; } int main () { freopen("odd.in", "r", stdin); freopen("odd.out", "w", stdout); int N; srand(20010625); scanf("%d", &N); for(int i = 1; i<=N; i++) { scanf("%d", &A[i]); if(!rd[A[i]]) rd[A[i]] = (UI)rand()*rand()*rand()^((ULL)rand()<<33)*rand()*rand(); } blocksz = floor(sqrt(N)); int cur = 1, t = 1; LL ans = 0; for(int i = 1; i<=N; i++) { blocks[cur].add(0, 1); if(lst[A[i]]) intervalXor(lst[A[i]], rd[A[i]]); ans += query(i, cur); lst[A[i]] = i; if(t == blocksz) ++cur, t = 1; else t ++; } printf("%I64d\n", ans); }
Join the discussion