P4137 Rmq Problem / mex

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200000 + 5;
int n, m;
int mm;         // 块的大小
int qid[MAXN];  // qid[i]: i/m，第i个数所属的块，块 id 从 0 开始
int qcnt[MAXN]; // qcnt[i]: 第i个块里面出现了多少个不同的数
int qall[MAXN]; // qall[i]: 第i个块里面一共有多少个数
int a[MAXN], maxAi;
int cnt[MAXN];
struct Q
{
    int l, r, id, ans;
} q[MAXN];
bool cmp(Q a, Q b)
{
    if (qid[a.l] != qid[b.l])
        return qid[a.l] < qid[b.l];
    return a.r < b.r;
}
bool cmpp(Q a, Q b)
{
    return a.id < b.id;
}
int nowAns;
// 添加了 a[x] 后，更新答案
void add(int x)
{
    cnt[a[x]]++;
    // 如果是新出现的数
    if (cnt[a[x]] == 1)
    {
        qcnt[qid[a[x]]]++;
        // 如果原来的答案现在出现了，更新答案
        if (a[x] == nowAns)
        {
            // 先找到是哪个块，再来定位是哪个数
            // 从这个块开始往后找
            int nowq = qid[a[x]];
            // 如果当前块的数全出现过了，那就肯定不在这个块里，去下个块找
            while (qcnt[nowq] == qall[nowq])
                nowq++;
            // 先认为答案是第 nowq 个块的第一个数 (0,mm-1) (mm,2mm-1) (2mm,3mm-1)
            nowAns = nowq * mm;
            // 如果不是这个就暴力跳到下一个
            while (cnt[nowAns] != 0)
                nowAns++;
        }
    }
}
void del(int x)
{
    cnt[a[x]]--;
    if (cnt[a[x]] == 0)
    {
        nowAns = min(a[x], nowAns);
        qcnt[qid[a[x]]]--;
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    //1~n 每个位置分块，求出 qid[i]: 第 i 个位置所属的块
    mm = sqrt(n);
    maxAi = 0;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        maxAi = max(maxAi, a[i]);
        qid[i] = i / mm;
    }
    for (int i = 1; i <= m; i++)
    {
        cin >> q[i].l >> q[i].r;
        q[i].id = i;
    }
    // 对询问排序
    // 左端点所属的块相同时按照右端点排序，不同时按照左端点所属的块排序
    sort(q + 1, q + m + 1, cmp);
    // 排完序后复用前面的qid数组，完成对cnt数组的分块
    // cnt[i]: 数字i的出现次数
    //  qid[i]: i/m，第i个数所属的块，块 id 从 0 开始
    //  qcnt[i]: 第i个块里面出现了多少个不同的数
    //  qall[i]: 第i个块里面一共有多少个数
    mm = sqrt(maxAi + 1);
    // 0:(0,mm-1) 1:(mm,2mm-1) 2:(2mm,3mm-1)
    for (int i = 0; i <= maxAi + 1; i++)
    {
        cnt[i] = 0;
        qid[i] = i / mm;
        qall[qid[i]]++;
        qcnt[qid[i]] = 0;
    }
    // 把排完序的询问一条条处理答案
    // 初始设置为第一个区间
    int L = q[1].l;
    int R = q[1].r;
    nowAns = 0;
    for (int i = L; i <= R; i++)
        add(i);
    q[1].ans = nowAns;
    // 第二个区间开始由上一个区间转移得到
    for (int i = 2; i <= m; i++)
    {
        while (q[i].l < L)
            add(--L);
        while (q[i].l > L)
            del(L++);
        while (q[i].r < R)
            del(R--);
        while (q[i].r > R)
            add(++R);
        q[i].ans = nowAns;
    }
    // 重新按照问题 id 排序，输出每个问题的答案
    sort(q + 1, q + m + 1, cmpp);
    for (int i = 1; i <= m; i++)
        cout << q[i].ans << "\n";
    return 0;
}