题意：
求所有子数组的 M E X MEX MEX组成的序列的 M E X MEX MEX
题解：
首先，如果要使 M E X MEX MEX 为 x x x ,则必须满足：
1. 1. 1. ( 1 , x − 1 ) (1,x-1) (1,x−1) 都出现过
2. 2. 2. x x x 没出现过
那么怎么求出这些 x x x 呢，考虑暴力一点的做法，枚举右端点 i i i ,考虑是否存在区间使得 M E X MEX MEX为 x x x ,那么利用权值线段树维护每个值的最近出现的位置，求出 ( 1 , x − 1 ) (1,x-1) (1,x−1)的最小的位置 p p p，如果最后一次出现 x x x 的位置在 p p p 之前，那么说明可以得到 x x x 。但是这样枚举肯定会 t l e tle tle 。再观察，下一个 x x x 出现的位置肯定在 i i i 之后。那么我们对 x x x 枚举下一个出现的位置，然后考虑上一个出现的位置是否小于 p p p 。通俗的讲，就是枚举数组的每个位置，看上一个 a [ i ] a[i] a[i]出现的位置是否在 p p p 之前即可。
代码：
#pragma GCC diagnostic error "-std=c++11"
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#define iss ios::sync_with_stdio(false)
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
const int mod = 1e9 + 7;
const int MAXN = 2e5 + 5;
const int inf = 0x3f3f3f3f;
int a[MAXN];
int vis[MAXN], pre[MAXN];
struct node {
int l, r;
int mi;
/* data */
} node[MAXN << 2];
void build(int l, int r, int num)
{
node[num].l = l;
node[num].r = r;
if (l == r) {
node[num].mi = 0;
return;
}
int mid = (l + r) >> 1;
build(l, mid, num << 1);
build(mid + 1, r, num << 1 | 1);
node[num].mi = min(node[num << 1].mi, node[num << 1 | 1].mi);
}
void updata(int pos, int val, int num)
{
if (node[num].l == node[num].r) {
node[num].mi = val;
return;
}
int mid = (node[num].l + node[num].r) >> 1;
if (pos <= mid)
updata(pos, val, num << 1);
else
updata(pos, val, num << 1 | 1);
node[num].mi = min(node[num << 1].mi, node[num << 1 | 1].mi);
}
int query(int l, int r, int num)
{
if (node[num].l >= l && node[num].r <= r) {
return node[num].mi;
}
int mid = (node[num].l + node[num].r) >> 1;
int mi = 1e9;
if (l <= mid)
mi = min(mi, query(l, r, num << 1));
if (r > mid)
mi = min(mi, query(l, r, num << 1 | 1));
return mi;
}
int main()
{
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
for (int i = 1; i <= n + 2; i++)
pre[i] = 0;
build(1, n + 2, 1);
for (int i = 1; i <= n; i++) {
if (a[i] > 1) {
vis[1] = 1;
int pos = query(1, a[i] - 1, 1);
if (pos>pre[a[i]]){
vis[a[i]] = 1;
}
}
updata(a[i], i, 1);
pre[a[i]] = i;
}
for (int i = 2; i <= n + 2; i++){
if(query(1,i-1,1)>pre[i]){
vis[i] = 1;
}
}
for (int i = 1; i <= n + 2;i++){
if(!vis[i]){
cout << i << endl;
return 0;
}
}
}