Codeforces 703D - Mishka and Interesting sum

#数据结构 #技巧 #树状数组 #离线 #异或
Published on 2016-08-05

题目地址

描述

有一个长度为 n(n≤1000000)n(n\le 1000000) 的序列 。现在有 m(m≤1000000)m(m\le 1000000) 个询问，每次询问区间 [l,r][l, r] 内出现偶数次的数的异或和。

分析

询问区间 [l,r][l, r] 内出现偶数次的数的异或和，不太好办，我们先看看将 [l,r][l, r] 所有的数直接异或起来会怎么样：
根据异或的性质 a xor a=0a\ \mathrm{xor}\ a = 0 且 a xor 0=aa\ \mathrm{xor}\ 0 = a，我们发现全部异或起来，实际上得到的是出现奇数次的数的异或和，怎么得到出现偶数次的数的异或和呢？
只需将区间 [l,r][l, r] 的异或和，异或上区间内所有种类的数的异或和（即一同个数只异或一次）即可，考虑到异或的性质，我们可以采用 BZOJ 1878 - [SDOI2009]HH的项链 一样的方法处理即可。
复杂度： O(nlogn)O(n\log n)。

这题莫队不能过，会达到 109{10}^9 级别。

代码

//  Created by Sengxian on 8/4/16.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  Codeforces 703D 离线 + 树状数组
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
inline int ReadInt() {
    static int n, ch;
    n = 0, ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) n = (n << 3) + (n << 1) + ch - '0', ch = getchar();
    return n;
}

const int maxn = 1000000 + 3;
int n, a[maxn], vs[maxn], pos[maxn], ans[maxn], s[maxn], pre[maxn];
int nxt[maxn];

struct query {
    int l, r, id;
    inline bool operator < (const query &ano) const {
        return l < ano.l;
    }
}qs[maxn];

#define lowbit(x) ((x) & -(x))
inline void add(int p, int v) {
    for (int i = p + 1; i <= n; i += lowbit(i)) s[i] ^= v;
}

inline int sum(int x) {
    int ret = 0;
    for (int i = x + 1; i > 0; i -= lowbit(i)) ret ^= s[i];
    return ret;
}

int main() {
    n = ReadInt();
    for (int i = 0; i < n; ++i) pre[i] = vs[i] = a[i] = ReadInt();
    for (int i = 1; i < n; ++i) pre[i] ^= pre[i - 1];
    sort(vs, vs + n);
    int tmp = unique(vs, vs + n) - vs;
    for (int i = 0; i < n; ++i) a[i] = lower_bound(vs, vs + tmp, a[i]) - vs;


    memset(pos, -1, sizeof pos);
    for (int i = n - 1; ~i; --i) {
        if (~pos[a[i]]) nxt[i] = pos[a[i]];
        pos[a[i]] = i;
    }

    for (int i = 0; i < tmp; ++i) if (~pos[i]) add(pos[i], vs[i]);
    int m = ReadInt();
    for (int i = 0; i < m; ++i)
        qs[i].l = ReadInt() - 1, qs[i].r = ReadInt() - 1, qs[i].id = i;
    sort(qs, qs + m);
    int l = 0;
    for (int i = 0; i < m; ++i) {
        while (l < qs[i].l) {
            if (nxt[l]) add(nxt[l], vs[a[nxt[l]]]);
            l++;
        }
        ans[qs[i].id] = sum(qs[i].r) ^ sum(qs[i].l - 1) ^ pre[qs[i].r] ^ (qs[i].l == 0 ? 0 : pre[qs[i].l - 1]);
    }
    for (int i = 0; i < m; ++i) printf("%d\n", ans[i]);
    return 0;
}
HDOJ 5808 - Price List Strike Back