欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

P4137 Rmq Problem / mex (莫队)

程序员文章站 2022-03-30 22:17:34
题目 "P4137 Rmq Problem / mex" 解析 莫队算法维护mex, 往里添加数的时候,若添加的数等于$mex$,$mex$就不能等于这个值了,就从这个数开始枚举找$mex$;若不等于$mex$,没有影响. 取出数的时候,如果这个数出现的次数变为了$0$,$mex$就和这个数取一个$ ......

题目

p4137 rmq problem / mex

解析

莫队算法维护mex,

  • 往里添加数的时候,若添加的数等于\(mex\)\(mex\)就不能等于这个值了,就从这个数开始枚举找\(mex\);若不等于\(mex\),没有影响.
  • 取出数的时候,如果这个数出现的次数变为了\(0\)\(mex\)就和这个数取一个\(min\)

    代码

#include <bits/stdc++.h>
using namespace std;
const int n = 1e6 + 10;
int n, m, mex;
int a[n], cnt[n], ans[n];
class node {
    public :
        int l, r, id, bl;
        bool operator < (const node &oth) const {
            return this->bl == oth.bl ? this->r < oth.r : this->l < oth.l;
        }
} e[n];

template<class t>inline void read(t &x) {
    x = 0; int f = 0; char ch = getchar();
    while (!isdigit(ch)) f |= (ch == '-'), ch = getchar();
    while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
    x = f ? -x : x; 
    return ;
} 

inline void add(int x) {
    cnt[a[x]]++;
    int i = mex;
    if (a[x] == mex) while (cnt[i]) i++;
    mex = i;
}

inline void del(int x) {
    cnt[a[x]]--;
    if (cnt[a[x]] == 0) mex = min(mex, a[x]);
}

int main() {
    read(n), read(m);
    int k = sqrt(n);
    for (int i = 1; i <= n; ++i) read(a[i]);
    for (int i = 1, x, y; i <= m; ++i) {
        read(x), read(y);
        e[i] = (node) {x, y, i, x / k + 1};
    }
    sort(e + 1, e + 1 + m);
    int l = 1, r = 0;
    for (int i = 1; i <= m; ++i) {
        int ll = e[i].l, rr = e[i].r;
        while (l < ll) del(l++);
        while (l > ll) add(--l);
        while (r < rr) add(++r);
        while (r > rr) del(r--);
        ans[e[i].id] = mex;
    }
    for (int i = 1; i <= m; ++i) printf("%d\n", ans[i]);
    return 0;
}