P4137 Rmq Problem / mex 【莫队】【主席树+思维】

传送门

题目上给的 ai <= 1e9，第一反应就是离散化，细想一下区间一共就2e5，答案最大不就是2e5吗，大于2e5的数我们可以忽略，这样就可以减去离散化的步骤。

莫队解题思路：莫队的就是优雅的暴力，我们可以直接暴力去找答案（稍微优雅一下），我们记录当前区间中每个数出现的位置，当我们的区间移动时。增加操作：如果增加的数==Ans，那我们的答案就会更新，然后暴力向后判断(只有这里最暴力。。)。否则根本不会影响答案的改变。删除操作：如果删除的数 > Ans，根本不影响答案。否则只有当删除点这个数后，如果这个数的数量为0，那么答案就会更新。

代码：

#include<bits/stdc++.h>

using namespace std;
const int maxn = 2e5 + 5;

int n, q, num[maxn];
int L = 1, R = 0, Ans = 0, pos[maxn], cnt[maxn], ans[maxn];
struct node {
    int l, r, id;
} Q[maxn];

bool cmp(node a, node b) {  ///分块奇偶剪枝
    if (pos[a.l] == pos[b.l]) {
        if (pos[a.l] & 1) return a.r < b.r;
        return a.r > b.r;
    }
    return a.l < b.l;
}

void add(int x) {
    if (num[x] > maxn) return;
    if (num[x] == Ans) {
        cnt[num[x]]++;
        while (cnt[Ans] != 0) Ans++;
    } else cnt[num[x]]++;
}

void del(int x) {
    if (num[x] > maxn) return;
    if (num[x] >= Ans) cnt[num[x]]--;
    else { if (--cnt[num[x]] == 0) Ans = num[x]; }
}

int main() {
    scanf("%d %d", &n, &q);
    int sz = sqrt(n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &num[i]);
        pos[i] = i / sz;
    }
    for (int i = 1; i <= q; i++) {
        scanf("%d %d", &Q[i].l, &Q[i].r);
        Q[i].id = i;
    }
    sort(Q + 1, Q + 1 + q, cmp);
    for (int i = 1; i <= q; 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);
        ans[Q[i].id] = Ans;
    }
    for (int i = 1; i <= q; i++) printf("%d\n", ans[i]);
    return 0;
}

主席树解题思路：本来想用主席树维护每个数字出现的数字，然后利用差分得到区间信息，但是发现根本没办法得到答案。然后又想到了HH的项链，将相同的数字右移，但是我们是用维护的下标信息，我们得不到数字的信息，这种想法也不行。最后还是向现实低下了头（博客大法好）。
大佬的思路：每个主席树维护的信息：维护 [ 1 , i ]所有数最后出现的位置，维护一个值：区间中所有数最后出现位置的最小值。
那么我们查找的答案就是最后出现位置 小于 l 的最小值。
听着是不是很绕。。。然后我们可以去二分查找答案。

对于上面的那个图来讲：如果我们询问[4,7] 区间，我们就要在第7棵线段树上去二分查找答案，如果[0,2]中所有数字最后出现位置的最小值都>=4，说明[0,2]中的所有数都在[4,7]区间中出现过（否则我们就会在[0,2]中继续寻找）。[0,2]区间维护的最小值=5>4。那么答案锁定在[3,5]区间，我们继续二分去查找。知道查找到 l==r 时，就是我们要找的答案。

代码：

#include<bits/stdc++.h>

using namespace std;
const int maxn = 2e5 + 5;

int n, q, x;
struct node {
    int ls, rs, minn;
} p[maxn * 40];
int root[maxn], times;

///记录区间中每个值最后出现的下标的最小值
void pushup(int sign) {
    p[sign].minn = min(p[p[sign].ls].minn, p[p[sign].rs].minn);
}

/// 更新每个值最后出现的下标
void insert(int &now, int old, int l, int r, int x, int sub) {
    now = ++times, p[now] = p[old];
    if (l == r) {       ///可以直接覆盖，下标肯定是比原来大的
        p[now].minn = sub;
        return;
    }
    int mid = (l + r) >> 1;
    if (x <= mid) insert(p[now].ls, p[old].ls, l, mid, x, sub);
    else insert(p[now].rs, p[old].rs, mid + 1, r, x, sub);
    pushup(now);
}

///如果[l,mid]中的最小值<sub,则说明有数字没有在询问的区间中出现过
///如果均大于等于sub,那说明答案在[mid+1,r]区间中
int query(int now, int l, int r, int sub) {
    if (l == r) return l;
    int mid = (l + r) >> 1;
    if (p[p[now].ls].minn < sub) return query(p[now].ls, l, mid, sub);
    else return query(p[now].rs, mid + 1, r, sub);
}

int main() {
    int l, r;
    scanf("%d %d", &n, &q);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &x);
        if (x > maxn - 5) {        ///要求连续得自然数，大于2e5的数字可以不用考虑
            root[i] = root[i - 1];
            continue;
        }
        insert(root[i], root[i - 1], 0, maxn, x, i);
    }
    for (int i = 1; i <= q; i++) {
        scanf("%d %d", &l, &r);
        printf("%d\n", query(root[r], 0, maxn, l));
    }
    return 0;
}