题解：P11570 「chaynOI R1 T3」镍铬合金机器人

lovely_nst · 2025-01-13 23:14:39 · 题解

P11570 「chaynOI R1 T3」镍铬合金机器人

前言

这道我场切的，但是赛后发现题解是高贵的单 \log 做法，而我是低贱的双 \log 做法。

那就讲一下双 \log 的做法吧。

正文

首先要会求区间 \text{mex}。设 mx_{i,j}=\text{mex}(\{a_i,a_{i+1},\dots ,a_j\})(i\le j)，nxt_x 为 x 后下一个 a_y=a_x 的 y，若没有则等于 n+1。那如果已经确定了 mx_i，要转移到 mx_{i+1} 该如何转化？那无疑就是少了个 a_i 使 \text{mex} 变小，也就是原本只有一个 a_i，现在推掉了。易得，在 i+1 到 nxt_i-1 的 \text{mex} 可能改变，用线段树处理最小值即可。

其次，因为 \text{mex} 是递增的，因此二分即可。

AC Code

#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9 + 7;
int n , m , a[300005] , lst[300005] , nxt[300005] , mex[300005] , cnt[300005];
vector <pair <int , pair <int , int> > > q[300005];
int ans[300005] , d[2000005] , vis[2000005];

void build (int l , int r , int p)
{
    if (l == r)
    {
        d[p] = mex[l];
        return ;
    }
    int mid = l + ((r - l) >> 1);
    build (l , mid , p << 1);
    build (mid + 1 , r , p << 1 | 1);
    vis[p] = inf;
    d[p] = min (d[p << 1] , d[p << 1 | 1]);
}

int query (int l , int s , int t , int p)
{
    if (s == t)
        return d[p];
    int m = s + ((t - s) >> 1);
    if (vis[p] != inf)
    {
        d[p << 1]       =   min (d[p << 1]       , vis[p]);
        d[p << 1 | 1]   =   min (d[p << 1 | 1]   , vis[p]);
        vis[p << 1]     =   min (vis[p << 1]     , vis[p]);
        vis[p << 1 | 1] =   min (vis[p << 1 | 1] , vis[p]);
        vis[p] = inf;
    }
    int sum = inf;
    if (l <= m)
        sum = min (sum , query (l , s , m , p << 1));
    if (l > m)
        sum = min (sum , query (l , m + 1 , t , p << 1 | 1));
    return sum;
}

void update (int l , int r , int c , int s , int t , int p)
{
    if (l <= s && t <= r)
    {
        d[p] = min (d[p] , c) , vis[p] = min (vis[p] , c);
        return;
    }
    int m = s + ((t - s) >> 1);
    if (s != t)
    {
        d[p << 1]       =   min (d[p << 1]       , vis[p]);
        d[p << 1 | 1]   =   min (d[p << 1 | 1]   , vis[p]);
        vis[p << 1]     =   min (vis[p << 1]     , vis[p]);
        vis[p << 1 | 1] =   min (vis[p << 1 | 1] , vis[p]);
        vis[p] = inf;
    }
    if (l <= m) update (l , r , c , s , m , p << 1);
    if (r > m) update (l , r , c , m + 1 , t , p << 1 | 1);
    d[p] = min (d[p << 1] , d[p << 1 | 1]);
}
int chk (int i , int x)
{
    int l = i , r = n + 1 , mid;
    while (l < r)
    {
        mid = l + r >> 1;
        if (query (mid , 1 , n , 1) < x)
            l = mid + 1;
        else
            r = mid;
    }
    return r;
}
signed main ()
{
    cin.tie (0) , cout.tie (0) , ios::sync_with_stdio (0);
    cin >> n >> m;
    int p = 0;
    for (int i = 1;i <= n;i ++)
    {
        cin >> a[i] , cnt[a[i]] ++;
        nxt[lst[a[i]]] = i , lst[a[i]] = i;
        while (cnt[p]) p ++;
        mex[i] = p;
    }
    build (1 , n , 1);
    for (int i = 1;i <= m;i ++)
    {
        int l , x , y;
        cin >> l >> x >> y;
        q[l].push_back ({i , {x , y}});
    }
    for (int i = 1;i <= n;i ++)
    {
        for (auto it : q[i])
        {
            int id = it.first , x = it.second.first , y = it.second.second;
            int p1 = chk (i , x) , p2 = chk (i , y + 1);
            ans[id] = p2 - p1;
        }
        if (nxt[i] == 0) nxt[i] = n + 1;
        update (i , nxt[i] - 1 , a[i] , 1 , n , 1);
    }
    for (int i = 1;i <= m;i ++)
        cout << ans[i] << '\n';
    return 0;
}