Ta sẽ xử lý các truy vấn theo chiều ~r~ tăng dần.

Với mỗi phần tử từ ~1~ tới ~i~, ta sẽ lưu vị trí xuất hiện cuối cùng của nó. Ví dụ: nếu ta xử lý đến ~[3, 2, 1, 1, 3]~, ta sẽ lưu lại thành ~[0, 2, 0, 1, 3]~.

Sau đó, để trả lời truy vấn ~(l, i)~, ta chỉ cần lấy phép ~\text{xor}~ các số trong đoạn ~[l..i]~. Cả hai thao tác cập nhật và trả lời truy vấn đều có thể xử lý bằng fenwick tree.

Độ phức tạp: ~O((n + q)\ \text{log}\ n)~.

Code mẫu

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

#define fi first
#define se second
typedef long long ll;
typedef pair<ll, ll> ii;

const int N = 1e6 + 7;
int n, q, a[N], res[N];
map<int, int> last;
vector<ii> adj[N];

int T[N];
void upd(int pos, int val) {
    for (; pos <= n; pos += pos & -pos)
        T[pos] ^= val;
}

int get(int pos) {
    int res = 0;
    for (; pos; pos -= pos & -pos) res ^= T[pos];
    return res;
}

int get(int l, int r) {
    return get(r) ^ get(l - 1);
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> a[i]; 
    for (int i = 1, l, r; i <= q; i++) {
        cin >> l >> r;
        adj[r].push_back({l, i});
    }

    for (int i = 1; i <= n; i++) {
        if (last.find(a[i]) != last.end()) upd(last[a[i]], a[i]);
        last[a[i]] = i; upd(i, a[i]);

        for (auto [j, idx]: adj[i]) res[idx] = get(j, i);
    }   
    for (int i = 1; i <= q; i++) cout << res[i] << ' ';
}