[考试题目] 偶 分块

题目大意

有一个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);
}