很久之前就看过的题。不过一直没有勇气去做。爱真的需要勇气。
mex这个函数的性质比较奇妙。一端确定的话一定是单增的。两段和起来也一定是增加的。
可以很方便地求出从1到任何一个位置的mex。考虑把询问离线。按左端点排序。如果去掉一个数，那么对于右端点在（从这个数到下一个等于这个数的位置）这一段里的询问，它的值至多是这个数。
所以用线段树维护区修单查维护一下区间最小值就好了。注意如果没有下一个数了那么右端点是n。
据说要离散不过被我用map给水过去了。
#include <cstdio>
#include <cctype>
#include <memory.h>
#include <map>
#include <algorithm>
using namespace std;
#define readInt(_s_) {\
int _d_;\
_s_ = 0;\
while (!isdigit(_d_ = getchar()));\
while ((_s_ = _s_ * 10 + _d_ - 48), isdigit(_d_ = getchar()));\
}
struct seg {
int l, r, z;
seg *ls, *rs;
};
struct query {
int l, r, n;
};
inline bool cmpQuery(const query& a, const query& b) {
return a. l < b. l;
}
typedef pair <int, int> rpair;
const int maxn = 200009;
const int inf = 0x3f3f3f3f;
int n, m, a[maxn], tmp[maxn], nv[maxn], m0[maxn], ans[maxn];
bool fv[maxn];
seg *rt, *sp;
query q[maxn];
map <int, int> rp;
inline bool cmpTmp(const int& x, const int& y) {
return (a[x] < a[y]) || (a[x] == a[y] && x < y);
}
#define mid(p) ((p->l+p->r)>>1)
seg* sgtBuild(int l, int r) {
seg* p = sp ++;
p-> l = l;
p-> r = r;
p-> z = inf;
if (l + 1 < r) {
p-> ls = sgtBuild(l, mid(p));
p-> rs = sgtBuild(mid(p), r);
}
else
p-> z = m0[l];
return p;
}
void sgtChg(seg* p, int l, int r, int v) {
if (p-> l == l && p-> r == r)
p-> z = min(p-> z, v);
else if (r <= mid(p))
sgtChg(p-> ls, l, r, v);
else if (l >= mid(p))
sgtChg(p-> rs, l, r, v);
else {
sgtChg(p-> ls, l, mid(p), v);
sgtChg(p-> rs, mid(p), r, v);
}
}
int sgtQry(seg* p, int p0) {
if (p-> l + 1 == p-> r)
return p-> z;
else if (p0 < mid(p))
return min(sgtQry(p-> ls, p0), p-> z);
else
return min(sgtQry(p-> rs, p0), p-> z);
}
void preSeq() {
a[0] = -1;
for (int i = 0; i <= n; ++ i)
tmp[i] = i;
sort(tmp, tmp + n + 1, cmpTmp);
m0[n] = 0;
for (int i = 0; i <= n; ++ i) {
if (a[tmp[i]] == m0[n])
++ m0[n];
if (i && a[tmp[i]] > a[tmp[i - 1]])
fv[tmp[i]] = 1;
else
fv[tmp[i]] = 0;
}
nv[n] = -1;
for (int i = n; i; -- i) {
if (!fv[i] || a[i] > m0[i])
m0[i - 1] = m0[i];
else
m0[i - 1] = a[i];
map <int, int> :: iterator it = rp. find(a[i]);
if (it == rp. end()) {
nv[i] = -1;
rp. insert(rpair(a[i], i));
}
else {
nv[i] = it-> second;
it-> second = i;
}
}
sp = new seg[maxn * 3];
rt = sgtBuild(1, n + 1);
}
void rmvNum(int i) {
if (nv[i] > -1)
sgtChg(rt, i, nv[i], a[i]);
else
sgtChg(rt, i, n + 1, a[i]);
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
readInt(n);
readInt(m);
for (int i = 1; i <= n; ++ i)
readInt(a[i]);
for (int i = 0; i < m; ++ i) {
readInt(q[i]. l);
readInt(q[i]. r);
q[i]. n = i;
}
sort(q, q + m, cmpQuery);
preSeq();
for (int i = 0, j = 1; i < m; ++ i) {
for (; j < q[i]. l; ++ j)
rmvNum(j);
ans[q[i]. n] = sgtQry(rt, q[i]. r);
}
for (int i = 0; i < m; ++ i)
printf("%d\n", ans[i]);
}