LOJ #6187. Odd（随机+分块+hash表）

https://loj.ac/problem/6187

题解：

看到奇数时就应该想到随机的，最近两次遇到这种题了。

考虑给每一个数随机一个权值\(v[i]\)。

一个区间\([x,y]\)所有数的出现次数是奇数，相当于\(v[x..y]\)的异或和 等于 \(la[i]<x且x<=i<=y ~v[i]\)的异或和。

设\(s\)表示\(v\)的前缀异或和。

从左往右枚举\(y\)，记\(p[x]\)表示\(la[i]<x且x<=i<=y ~v[i]\)的异或和。

相当于求\(s[x-1]⊕p[x]⊕s[y]=0\)的\(x\)的数量。

随着\(y\)右移到\(y+1\),会使\(p[la[y+1]+1..y]⊕=v[y+1]\)

那么问题就变成了：
1.对p的一个区间异或上一个数

2.查询\(p\)中\(=s[y]\)的个数。

考虑用分块维护，每一块存一个hash表和lazytag以支持查询。

时间复杂度：\(O(n\sqrt n)\)

hash表分开建会快，从别人的代码里学到一个写hash表的新姿势：

struct hash_table {
    //...
    int& operator [] (long long n) {
        //...
    }
} h[N];
//在外面可以直接调用h[...][...]

Code：

#include<bits/stdc++.h>
#define fo(i, x, y) for(int i = x, _b = y; i <= _b; i ++)
#define ff(i, x, y) for(int i = x, _b = y; i <  _b; i ++)
#define fd(i, x, y) for(int i = x, _b = y; i >= _b; i --)
#define ll long long
#define pp printf
#define hh pp("\n")
using namespace std;

#define ul unsigned long long
ul rx = 1e9 + 7;
ll rand(ll x, ll y) {
    rx *= 998244353;
    return rx % (y - x + 1) + x;
}

const int M = 1e6 + 5;

ll rv[M];

const int N = 2e5 + 5;

int n;
ll a[N], s[N];
int la[N], ed[M];

void Init() {
    fo(i, 0, 1e6) rv[i] = rand(1, 1ll << 60);
    scanf("%d", &n);
    fo(i, 1, n) {
        scanf("%lld", &a[i]);
        la[i] = ed[a[i]];
        ed[a[i]] = i;
        a[i] = rv[a[i]];
        s[i] = s[i - 1] ^ a[i];
    }
}

namespace fk {
    const int blo = 400;
    const int C = N / blo + 5;
    
    const int M = 20007;
    struct nod {
        int fi[M], d[blo + 5], d0;
        int nt[blo + 5], cnt[blo + 5], td;
        ll h[blo + 5];
        void _new() {
            fo(i, 1, td) cnt[i] = 0;
            fo(i, 1, d0) fi[d[i]] = 0;
            td = d0 = 0;
        }
        int& operator [] (ll n) {
            int y = n % M;
            for(int p = fi[y]; p; p = nt[p])
                if(h[p] == n) return cnt[p];
            if(fi[y] == 0) d[++ d0] = y;
            nt[++ td] = fi[y], fi[y] = td, h[td] = n;
            return cnt[td];
        }
        int find(ll n) {
            int y = n % M;
            for(int p = fi[y]; p; p = nt[p]) 
                if(h[p] == n) return cnt[p];
            return 0;
        }
    } c[C];
    
    
    int id[N], id0, l[C], r[C];
    ll v[N], lz[C];
    
    void cg(int w) {
        c[w]._new();
        fo(i, l[w], r[w]) c[w][v[i]] ++;
    }
    void build() {
        fo(i, 1, n) {
            if(i % blo == 1) l[++ id0] = i;
            id[i] = id0; r[id0] = i;
        }
        fo(i, 1, n) v[i] = s[i - 1];
        fo(i, 1, id0) cg(i);
    }
    
    void cha_b(int x, int y, ll z) {
        fo(i, x, y) v[i] ^= z;
        cg(id[x]);
    }
    void cha(int x, int y, ll z) {
        if(id[x] == id[y]) return cha_b(x, y, z);
        cha_b(x, r[id[x]], z); cha_b(l[id[y]], y, z);
        fo(i, id[x] + 1, id[y] - 1) lz[i] ^= z;
    }
    
    int qry_b(int x, int y, ll z) {
        z ^= lz[id[x]]; int s = 0;
        fo(i, x, y) s += (z == v[i]);
        return s;
    }
    int qry(int x, int y, ll z) {
        if(id[x] == id[y]) return qry_b(x, y, z);
        int s = qry_b(x, r[id[x]], z) + qry_b(l[id[y]], y, z);
        fo(i, id[x] + 1, id[y] - 1) s += c[i].find(z ^ lz[i]);
        return s;
    }
}

void work() {
    ll ans = 0;
    fo(i, 1, n) {
        fk :: cha(la[i] + 1, i, a[i]);
        ans += fk :: qry(1, i, s[i]);
    }
    pp("%lld\n", ans);
}

int main() {
    Init();
    fk :: build();
    work();
}

LOJ #6187. Odd（随机+分块+hash表）

原文：https://www.cnblogs.com/coldchair/p/12447946.html