laekov

很久之前就看过的题。不过一直没有勇气去做。爱真的需要勇气。

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]);

}