szoj657 【AHSDFZNOI 7.2 WuHongxun】Odd

【题目大意】

给出$n$个数$a_1, a_2, ..., a_n$，求有多少个区间$[l, r]$，满足每个数都出现了奇数次。

$1 \leq n \leq 2 * 10^5, 0 \leq a_i \leq 10^6$

【题解】

稳爷爷出的noi模拟题（原题来自某地区ioi选拔赛）

给每个数赋一个随机权值$H_x$，那么问题转化为：

有多少个区间，使得区间内的数的异或和=区间内出现过的数的异或和。

这是可以分块的，记$lst_i$表示数$i$上一次出现的位置，令$x = H_{a_i}$那么每次就是给$[1, lst_x]$异或一个数，并且询问$[1, i]$中为0的数的个数。

分块+map可以做到$O(n\sqrt{nlogn})$。但是会被卡。

分块+hash就能做到$O(n\sqrt{n})$了，把hash表的取模开到1000~3000较优。每次暴力就重构一次。重构的时空复杂度是正确的。

# include <map>

# include <vector>

# include <stdio.h>

# include <string.h>

# include <iostream>

# include <algorithm>

// # include <bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef long double ld;

typedef unsigned long long ull;

const int N = 2e5 + , M = 1e6 + , NB =  + ;

const int mod = 1e9+, BLOCK = ;

const int MOD = ;

int n, m, B, a[N], bl[N], L[N], R[N];

vector<int> ps;

ull H[N];

int lst[N];

struct hasher {

    int head[MOD + ], w[MOD + ], nxt[MOD + ], tot, id, hid[MOD + ]; ull to[MOD + ];

    inline void set() {

        tot = ; id = ;

        memset(head, , sizeof head);

        memset(hid, , sizeof hid);

    }

    inline void reset() {

        tot = ; ++id;

    }

    inline void add(int u, ull v, int _w) {

        ++tot; nxt[tot] = head[u];

        head[u] = tot; to[tot] = v; w[tot] = _w;

    }

    inline void init(int L, int R) {

        add(, , R-L+);

    }

    inline int bg(int x) {

        if(hid[x] == id) return head[x];

        else {

            hid[x] = id;

            return head[x] = ;

        }

    }

    inline void ins(ull x) {

        int hx = x % MOD;

        for (int i=bg(hx); i; i=nxt[i])

            if(to[i] == x) {

                ++w[i];

                return ;

            }

        add(hx, x, );

    }

    inline int query(ull x) {

        int hx = x % MOD;

        for (int i=bg(hx); i; i=nxt[i])

            if(to[i] == x) return w[i];

        return ;

    }

}solver[NB];

inline ull irand() {

    ull ret = ;

    for (int i=; i<=; ++i) ret = (ret << ) + rand();

    return ret;

}

ull tag[NB], c[N];

inline void dealxor(int x, ull v) {

    if(!x) return ;

    int p = bl[x];

    for (int i=; i<p; ++i) tag[i] ^= v;

    solver[p].reset();

    for (int i=L[p]; i<=x; ++i) {

        c[i] ^= v;

        solver[p].ins(c[i]);

    }

    for (int i=x+; i<=R[p]; ++i) solver[p].ins(c[i]);

}

inline int query(int x) {

    int p = bl[x], ret = ;

    for (int i=; i<p; ++i) ret += solver[i].query(tag[i]);

    for (int i=L[p]; i<=x; ++i) if(c[i] == tag[p]) ++ret;

    return ret;

}

int main() {

//    freopen("odd2.in", "r", stdin);

    cin >> n;

    for (int i=; i<=n; ++i) {

        scanf("%d", a+i);

        ps.push_back(a[i]);

    }

    sort(ps.begin(), ps.end());

    ps.erase(unique(ps.begin(), ps.end()), ps.end());

    m = ps.size();

    for (int i=; i<=n; ++i) a[i] = lower_bound(ps.begin(), ps.end(), a[i]) - ps.begin() + ;

    for (int i=; i<=m; ++i) H[i] = irand();

    for (int i=; i<=n; ++i) bl[i] = (i-)/BLOCK + ;

    B = bl[n];

    for (int i=; i<=B; ++i) L[i] = (i-) * BLOCK + , R[i] = i * BLOCK;

    R[B] = min(R[B], n);

    for (int i=; i<=B; ++i) solver[i].set(), solver[i].init(L[i], R[i]);

    ll ans = ;

    for (int i=; i<=n; ++i) {

        int pre = lst[a[i]]; lst[a[i]] = i;

//        cerr << i << ' ' << pre << endl;

        dealxor(pre, H[a[i]]);

        ans += query(i);

    }

    cout << ans;

    return ;

}

/*

4

2 2 2 3

Ans = 7

*/

巴特西

szoj657 【AHSDFZNOI 7.2 WuHongxun】Odd

最新文章

热门文章