D.找更多的数字(题解)

前言

看一眼题目就想到了之前做过的cf上面一道主席树的题，码了半天才过，最后赛后一看过的人这么多，疑惑不解。看了眼题解区，原来有这么多简单做法，有利用数学方法解方程的，有利用异或结论，搞个前缀和直接秒的，这里就分享一下我的麻烦做法。

题意

给一个数组，多次询问，每次询问一个区间，保证区间内恰好有2个数只出现1次，其他数出现2次，输出只出现一次的这两个数。

分析

cf上面有个题，是判断区间恰好有一个数出现奇数次，其他是偶数次的，算是这题的进阶版本，直接沿用那题的思路，核心还是利用出现2次异或和为0.

对每个数随机一个大的权值，防止哈希碰撞。然后建一棵主席树，维护值域上的异或前缀和，利用主席树，就可以每次得到一个区间内，对应的每个值域的哈希异或和。然后在主席树上二分，如果左子树的异或和是0，说明值域在 内的数都是恰好出现2次。否则说明值域在 内的数至少有一个出现1次，则递归进去查找，右子树同理，递归到叶子则说明找到了，返回，一次查询恰好会有两个地方递归到叶子，单次查询的复杂度是 , 总的复杂度是 ，不过由于主席树的常数较大，实际跑起来甚至不如排行榜里面有个人用 set 模拟主席树乱搞来的快。

代码

#include <bits/stdc++.h>
#define int long long
#define inf 0x3f3f3f3f
#define ll long long
#define pii pair<int, int>
#define tii tuple<int, int, int>
#define db double
#define all(a) a.begin(), a.end()
using namespace std;
const int maxn = 1e6 + 10;
const int mod = 998244353;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int val[maxn], root[maxn];
vector<int> vec;
struct SegmentTree {
#define lson t[rt].ls
#define rson t[rt].rs
#define mid ((l + r) >> 1)
    struct Node {
        int ls, rs, sum;
    };
    int tot;
    vector<Node> t;
    SegmentTree(int n) { t.resize(n << 5); }
    void push_up(int rt) { t[rt].sum = t[lson].sum ^ t[rson].sum; }
    void modify(int& rt, int pre, int l, int r, int pos) {
        rt = ++tot;
        t[rt] = t[pre];
        if (l == r) {
            t[rt].sum ^= val[l];
            return;
        }
        if (pos <= mid)
            modify(lson, t[pre].ls, l, mid, pos);
        else
            modify(rson, t[pre].rs, mid + 1, r, pos);
        push_up(rt);
    }
    void query(int now, int pre, int l, int r) {
        if (l == r) {
            if (t[now].sum ^ t[pre].sum)
                vec.push_back(l);
            return;
        }
        if (t[t[now].ls].sum ^ t[t[pre].ls].sum)
            query(t[now].ls, t[pre].ls, l, mid);
        if (t[t[now].rs].sum ^ t[t[pre].rs].sum)
            query(t[now].rs, t[pre].rs, mid + 1, r);
    }
};
void solve() {
    for (int i = 0; i <= 1e6; i++)
        val[i] = rng();
    int n, q;
    cin >> n >> q;
    SegmentTree seg(n);
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        seg.modify(root[i], root[i - 1], 0, 1e6, x);
    }
    while (q--) {
        int l, r;
        cin >> l >> r;
        vec.clear();
        seg.query(root[r], root[l - 1], 0, 1e6);
        if (vec[0] > vec[1])
            swap(vec[0], vec[1]);
        assert(vec.size() == 2);
        cout << vec[0] << " " << vec[1] << "\n";
    }
}
signed main() {
    // freopen("1.in", "r", stdin);
    // freopen("1.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int t = 1;
    // cin >> t;
    while (t--)
        solve();
    return 0;
}