[C++知识库]CodeForces 1436 E. Complicated Computations(权值线段树)

传送门

题意：

求所有子数组的$MEX$?组成的序列的$MEX$

题解：

首先，如果要使$MEX$? 为$x$ ,则必须满足：

$1.$ $(1,x?1)$ 都出现过

$2.$ $x$ 没出现过

那么怎么求出这些 $x$ 呢，考虑暴力一点的做法，枚举右端点 $i$ ,考虑是否存在区间使得 $MEX$为 $x$ ,那么利用权值线段树维护每个值的最近出现的位置，求出$(1,x?1)$的最小的位置$p$，如果最后一次出现 $x$ 的位置在 $p$ 之前，那么说明可以得到 $x$ 。但是这样枚举肯定会 $tle$? 。再观察，下一个 $x$ 出现的位置肯定在 $i$ 之后。那么我们对 $x$ 枚举下一个出现的位置，然后考虑上一个出现的位置是否小于 $p$ 。通俗的讲，就是枚举数组的每个位置，看上一个$a[i]$出现的位置是否在 $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;
        }
    }
}