思路

• 关键性质 1（奇数次） 区间 $[l,r]$ 内所有元素“逐个按位置”做异或，等价于“出现奇数次的所有不同值”做异或，因为相同值的偶数次会互相抵消。 令前缀异或为 $S[i] = a_1 \oplus a_2 \oplus \cdots \oplus a_i$，则

  $O(l,r)$ = $a_l \oplus a_{l+1} \oplus \cdots \oplus a_r$ = $S[r] \oplus S[l-1].$

• 关键性质 2（偶数且至少两次） 令 $D(l,r)$ 为区间 $[l,r]$ 内“不同值各取一次”的异或；令 $O(l,r)$ 为上式“奇数次值”的异或，则

  $$E(l,r) = D(l,r) \oplus O(l,r).$$

  因为 $[l,r]$ 内的不同值集合可分为“奇数次的值”和“偶数且至少两次的值”，两部分不交，集合异或等于对称差的按值异或。

• 如何在 $O((n+q)\log n)$ 求 $D(l,r)$ 离线按 $r$ 递增处理，用树状数组维护“每个值的最后一次出现位置上挂着该值本身”，其余位置为 $0$。 当走到位置 $i$（值为 $x=a_i$）：

  • 若 $x$ 之前最后一次出现于位置 $p$，在树状数组位置 $p$ 处异或上 $x$ 将其“移除”。
  • 在位置 $i$ 处异或上 $x$ 将其“加入为最新出现”。 如此，任意时刻对 $[l,r]$ 的区间查询得到的就是“在 $[l,r]$ 内出现过的不同值”的按值异或，即 $D(l,r)$。

• 实现

  • 预处理 $S[i]$。
  • 对所有 $op=1$ 直接输出 $S[r]\oplus S[l-1]$。
  • 收集所有 $op=2$ 到按 $r$ 的桶，用上述树状数组离线得到 $D(l,r)$，再与 $O(l,r)=S[r]\oplus S[l-1]$ 异或得到答案。

• 复杂度：总体 $O((n+q)\log n)$，空间 $O(n)$。

C++

#include <bits/stdc++.h>
using namespace std;

struct BIT {
    int n;
    vector<int> t;
    BIT(int n=0): n(n), t(n+1, 0) {}
    void add(int i, int v) {
        for (; i <= n; i += i & -i) t[i] ^= v;
    }
    int sum(int i) {
        int r = 0;
        for (; i > 0; i -= i & -i) r ^= t[i];
        return r;
    }
    int range(int l, int r) {
        if (l > r) return 0;
        return sum(r) ^ sum(l - 1);
    }
};

struct Q {
    int l, idx;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    if (!(cin >> n >> q)) return 0;
    vector<int> a(n + 1), pre(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        pre[i] = pre[i - 1] ^ a[i]; // 前缀异或
    }

    vector<long long> ans(q);
    vector<vector<Q>> bucket(n + 1);
    vector<tuple<int,int,int>> queries; // (op,l,r)
    queries.reserve(q);
    for (int i = 0; i < q; ++i) {
        int op, l, r;
        cin >> op >> l >> r;
        queries.emplace_back(op, l, r);
        if (op == 1) {
            // 奇数次 => 直接用区间按位置异或
            ans[i] = pre[r] ^ pre[l - 1];
        } else {
            // 偶数且至少两次 => 需要 D(l,r)，先离线
            bucket[r].push_back({l, i});
        }
    }

    // 树状数组维护“各值的最后一次出现位置上挂着该值”
    BIT bit(n);
    unordered_map<int,int> last; // 值 -> 最后一次出现位置
    last.reserve(n * 2);

    for (int r = 1; r <= n; ++r) {
        int x = a[r];
        auto it = last.find(x);
        if (it != last.end()) {
            bit.add(it->second, x); // 移除旧位置
        }
        bit.add(r, x); // 加入新位置
        last[x] = r;

        // 回答所有以 r 结尾的 op=2 查询
        for (auto &qq : bucket[r]) {
            int l = qq.l;
            int idx = qq.idx;
            int D = bit.range(l, r);                 // 不同值异或
            int O = pre[r] ^ pre[l - 1];            // 奇数次值异或
            ans[idx] = D ^ O;                       // 偶数且至少两次
        }
    }

    // 按输入顺序输出
    for (int i = 0; i < q; ++i) {
        cout << ans[i] << '\n';
    }
    return 0;
}

Python

import sys

def input():
    return sys.stdin.readline().strip()

class BIT:
    # 树状数组，支持异或
    def __init__(self, n):
        self.n = n
        self.t = [0] * (n + 1)
    def add(self, i, v):
        n = self.n
        while i <= n:
            self.t[i] ^= v
            i += i & -i
    def sum(self, i):
        r = 0
        while i > 0:
            r ^= self.t[i]
            i -= i & -i
        return r
    def range(self, l, r):
        if l > r:
            return 0
        return self.sum(r) ^ self.sum(l - 1)

data = sys.stdin.buffer.read().split()
it = iter(data)
try:
    n = int(next(it))
    q = int(next(it))
except StopIteration:
    sys.exit()

a = [0] * (n + 1)
pre = [0] * (n + 1)
for i in range(1, n + 1):
    a[i] = int(next(it))
    pre[i] = pre[i - 1] ^ a[i]

ans = [0] * q
bucket = [[] for _ in range(n + 1)]  # 每个 r 的查询列表 (l, idx)
queries = []
for idx in range(q):
    op = int(next(it)); l = int(next(it)); r = int(next(it))
    queries.append((op, l, r))
    if op == 1:
        # 奇数次 => 直接区间按位置异或
        ans[idx] = pre[r] ^ pre[l - 1]
    else:
        # 偶数且至少两次 => 离线求 D(l,r)
        bucket[r].append((l, idx))

bit = BIT(n)
last = {}  # 值 -> 最后一次出现位置

for r in range(1, n + 1):
    x = a[r]
    if x in last:
        bit.add(last[x], x)  # 移除旧位置
    bit.add(r, x)            # 加入新位置
    last[x] = r

    for l, idx in bucket[r]:
        D = bit.range(l, r)            # 不同值异或
        O = pre[r] ^ pre[l - 1]        # 奇数次值异或
        ans[idx] = D ^ O               # 偶数且至少两次

out = '\n'.join(str(v) for v in ans)
sys.stdout.write(out + '\n')

Java

import java.io.*;
import java.util.*;

public class Main {
    // 树状数组，支持异或
    static class BIT {
        int n;
        int[] t;
        BIT(int n) { this.n = n; this.t = new int[n + 1]; }
        void add(int i, int v) {
            for (; i <= n; i += i & -i) t[i] ^= v;
        }
        int sum(int i) {
            int r = 0;
            for (; i > 0; i -= i & -i) r ^= t[i];
            return r;
        }
        int range(int l, int r) {
            if (l > r) return 0;
            return sum(r) ^ sum(l - 1);
        }
    }

    static class FastScanner {
        private final InputStream in;
        private final byte[] buffer = new byte[1 << 16];
        private int ptr = 0, len = 0;
        FastScanner(InputStream is) { in = is; }
        private int read() throws IOException {
            if (ptr >= len) {
                len = in.read(buffer);
                ptr = 0;
                if (len <= 0) return -1;
            }
            return buffer[ptr++];
        }
        int nextInt() throws IOException {
            int c, sgn = 1, x = 0;
            do { c = read(); } while (c <= 32);
            if (c == '-') { sgn = -1; c = read(); }
            while (c > 32) {
                x = x * 10 + (c - '0');
                c = read();
            }
            return x * sgn;
        }
    }

    static class Q {
        int l, idx;
        Q(int l, int idx) { this.l = l; this.idx = idx; }
    }

    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner(System.in);
        int n = fs.nextInt();
        int q = fs.nextInt();
        int[] a = new int[n + 1];
        int[] pre = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            a[i] = fs.nextInt();
            pre[i] = pre[i - 1] ^ a[i]; // 前缀异或
        }

        long[] ans = new long[q];
        @SuppressWarnings("unchecked")
        ArrayList<Q>[] bucket = new ArrayList[n + 1];
        for (int i = 0; i <= n; i++) bucket[i] = new ArrayList<>();

        int[] opArr = new int[q];
        int[] lArr = new int[q];
        int[] rArr = new int[q];
        for (int i = 0; i < q; i++) {
            int op = fs.nextInt(), l = fs.nextInt(), r = fs.nextInt();
            opArr[i] = op; lArr[i] = l; rArr[i] = r;
            if (op == 1) {
                ans[i] = pre[r] ^ pre[l - 1]; // 奇数次 => 区间按位置异或
            } else {
                bucket[r].add(new Q(l, i));   // 偶数且至少两次 => 离线
            }
        }

        BIT bit = new BIT(n);
        HashMap<Integer, Integer> last = new HashMap<>(n * 2);
        for (int r = 1; r <= n; r++) {
            int x = a[r];
            Integer p = last.get(x);
            if (p != null) bit.add(p, x); // 移除旧位置
            bit.add(r, x);                // 加入新位置
            last.put(x, r);

            for (Q qq : bucket[r]) {
                int l = qq.l, idx = qq.idx;
                int D = bit.range(l, r);           // 不同值异或
                int O = pre[r] ^ pre[l - 1];       // 奇数次值异或
                ans[idx] = D ^ O;                  // 偶数且至少两次
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < q; i++) {
            sb.append(ans[i]).append('\n');
        }
        System.out.print(sb.toString());
    }
}

题目内容

给定一个包含 $n$ 个正整数的数组 $a_1,a_2,…,a_n$ ，以及 $q$ 次区间查询。查询有两种类型：

• 类型一：对区间 $[l,r]$ 中出现奇数次的所有值(即出现次数对 $2$ 取模为 $1$ 且至少出现一次)，将这些值逐一提取并计算异或和；

• 类型二：对区间 $[l,r]$ 中出现偶数次的所有值(即出现次数对 $2$ 取模为 $0$ 且至少出现两次)，将这些值逐一提取并计算异或和。

若区间内无符合条件的值，则结果为 $0$ 。

输入描述

第一行输入两个整数 $n,q(1≦n,q≦10^5)$ ，分别表示数组长度和查询次数。

第二行输入 $n$ 个整数 $a_1,a_2,…..,a_n(1≦a≦10^9)$ ，表示数组。

接下来 $q$ 行，每行输入三个整数op,l,™(1 ≤ op ≤ 2; 1≤l≤r≤n)，表示查询类型及区间左右端点。查询类型与题目描述一致。

输出描述

对每个查询，新起一行输出一个整数，表示对应区间的异或和结果。

样例1

输入

10 5
1 2 2 3 1 5 8 9 1 7
1 1 2
1 5 9
2 1 2
2 5 9
2 2 9

输出

3
4
0
1
3

说明

对于第一个查询：区间 $[1,2]=${$1,2$}，两者都出现一次(奇数次)，异或和 $1$ $xor$ $2=3$ ；

对于第二个查询：区间 $[5,9]=${$1,5,8,9,1$}，出现奇数次的值为 {$5,8,9$}，异或和 $5$ $xor$ $8$ $xor$ $9=4$ ；

对于第三个查询：区间 $[1,2]=${$1,2$}，无值出现偶数次，结果为 0；

对于第四个查询：区间 $[5,9]=${$1,5,8,9,1$}，仅值 $1$ 出现两次，异或和 $1$ ；

对于第五个查询：区间 $[2,9]=${$2,2,3,1,5,8,9,1$}，出现偶数次的值为 {$2,1$} ，异或和 $2$ $xor$ $1=3$ 。