[CF1436E] Complicated Computations

[CF1436E] Complicated Computations - 线段树,离线

Description

求一个数列的所有连续子数列的 mex 值的 mex。

Solution

值为 (i) 的元素将序列划分为若干段，每段内 (0..i-1) 都出现则合法

即检查若干区间内 (0..i-1) 是否都出现

离线后按右端点排序，扫描到 (r)，用线段树维护每个值得最晚出现位置，查询 (0..k-1) 的最小值，如果大于等于 (l) 则合法

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 4e5 + 5;

int val[N];

void pushup(int p)
{
    val[p] = min(val[p * 2], val[p * 2 + 1]);
}

void modify(int p, int l, int r, int ql, int qr, int v)
{
    if (l > qr || r < ql)
        return;
    if (l >= ql && r <= qr)
    {
        val[p] = v;
    }
    else
    {
        modify(p * 2, l, (l + r) / 2, ql, qr, v);
        modify(p * 2 + 1, (l + r) / 2 + 1, r, ql, qr, v);
        pushup(p);
    }
}

int query(int p, int l, int r, int ql, int qr)
{
    if (l > qr || r < ql)
        return 1e9;
    if (l >= ql && r <= qr)
        return val[p];
    return min(query(p * 2, l, (l + r) / 2, ql, qr), query(p * 2 + 1, (l + r) / 2 + 1, r, ql, qr));
}

int n, a[N];

signed main()
{
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    vector<tuple<int, int, int>> asks;
    vector<vector<int>> pos(n + 2);
    for (int i = 1; i <= n + 1; i++)
        pos[i].push_back(0);
    for (int i = 1; i <= n + 1; i++)
        pos[a[i]].push_back(i);
    for (int i = 1; i <= n + 1; i++)
        pos[i].push_back(n + 1);
    for (int i = 1; i <= n + 1; i++)
        for (int j = 1; j < pos[i].size(); j++)
            if (pos[i][j - 1] + 1 < pos[i][j])
                asks.push_back({pos[i][j] - 1, pos[i][j - 1] + 1, i - 1});
    sort(asks.begin(), asks.end());
    int cur = 0;
    set<int> s;
    for (int i = 0; i < asks.size(); i++)
    {
        auto [r, l, k] = asks[i];
        while (cur < r)
            ++cur, modify(1, 1, n, a[cur], a[cur], cur);
        if (query(1, 1, n, 1, k) >= l)
            s.insert(k + 1);
    }
    int ans = 1;
    while (s.find(ans) != s.end())
        ++ans;
    cout << ans << endl;
}