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

Copy

#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] << ' ';
}