ABC470G 唐诗题解

mysterys · 2026-08-09 21:53:01 · 题解

你说得对，但是我场上会这个后没写完。

首先，有个东西叫做极短 \operatorname{mex} 区间。

对于任意区间 [l, r]，其 \operatorname{mex} 等于所有被包含的极短 \operatorname{mex} 区间的 \operatorname{mex} 最大值。

我们可以先预处理所有极短 \operatorname{mex} 区间，然后考虑如何计算答案。

应该有扫描线矩形并做法，但是我没细想。

下面介绍另一种做法：

考虑对右端点扫描线，每次在右端点加入一个极短 \operatorname{mex} 区间 [l,r]，考虑它对答案的影响：所有左端点在 l 左侧的区间且原本 \operatorname{mex} 比现在加入的 \operatorname{mex} 小的区间，答案都变为\operatorname{mex}，所以相当于一个前缀 chechkmax。所以我们扫描线，然后用吉司机线段树维护前缀 chechkmax 和区间求和即可。

:::info[Code]

#include<bits/stdc++.h>
using namespace std;
#define FILE(x) freopen(x".in","r",stdin); freopen(x".out","w",stdout);
#define ll long long
#define pii pair<int, int>
#define mk make_pair
#define fi first
#define se second
const int N = 3e5 + 5, inf = 1e9;
vector<pii>g[N], add[N];
vector<int>pos[N];
int n, a[N], rt[N];
int cnt;
namespace T{
    #define ls(u) (t[u].l)
    #define rs(u) (t[u].r)
    struct node{
        int l, r, v;
    }t[N * 25];
    inline void up(int u){ 
        t[u].v = min(t[ls(u)].v, t[rs(u)].v);
    }
    inline void upd(int& u, int pre, int l, int r, int k, int v){
        t[u = ++cnt] = t[pre]; 
        if(l == r) return t[u].v = v, void();
        int mid = (l + r) >> 1;
        k <= mid ? upd(ls(u), ls(pre), l, mid, k, v) : upd(rs(u), rs(pre), mid + 1, r, k, v);
        up(u);
    }
    inline int ask(int u, int l, int r, int k){
        if(l == r) return l;
        int mid = (l + r) >> 1;
        return t[ls(u)].v < k ? ask(ls(u), l, mid, k) : ask(rs(u), mid + 1, r, k);
    }
    #undef ls
    #undef rs
}
inline int mex(int l, int r){ return T::ask(rt[r], 0, n, l); }
inline int get_pre(int x, int id){
    auto it = lower_bound(pos[id].begin(), pos[id].end(), x);
    return it == pos[id].begin() ? 0 : *prev(it);
}
inline int get_nxt(int x, int id){
    auto it = upper_bound(pos[id].begin(), pos[id].end(), x);
    return it == pos[id].end() ? n + 1  : *it;
}
namespace SGT{
    #define ls (u << 1)
    #define rs (u << 1 | 1)
    struct node{
        int mn, se, cnt, lzy;
        ll sum;
    }t[N << 2];
    inline void up(int u){
        t[u].sum = t[ls].sum + t[rs].sum;
        if(t[ls].mn == t[rs].mn) {
            t[u].mn = t[ls].mn;
            t[u].cnt = t[ls].cnt + t[rs].cnt;
            t[u].se = min(t[ls].se, t[rs].se);
        }else {
            t[u].mn = min(t[ls].mn, t[rs].mn);
            t[u].cnt = t[ls].mn < t[rs].mn ? t[ls].cnt : t[rs].cnt;
            t[u].se = t[ls].mn < t[rs].mn ? min(t[ls].se, t[rs].mn) : min(t[rs].se, t[ls].mn);
        }
    }
    inline void f(int u, int v){
        if(t[u].mn >= v) return;
        t[u].sum += 1ll * t[u].cnt * (v - t[u].mn);
        t[u].mn = t[u].lzy = v;
    }
    inline void down(int u){
        if(t[u].lzy == inf) return;
        f(ls, t[u].lzy), f(rs, t[u].lzy);
        t[u].lzy = inf;
    }
    inline void build(int u, int l, int r){
        t[u].lzy = inf;
        if(l == r) return t[u].cnt = 1, t[u].se = inf, void();
        int mid = (l + r) >> 1;
        build(ls, l, mid), build(rs, mid + 1, r);
        up(u);
    }
    inline void upd(int u, int l, int r, int ql, int qr, int v){
        if(t[u].mn >= v) return;
        if(l >= ql && r <= qr && t[u].se > v) return f(u, v), void();
        int mid = (l + r) >> 1; down(u);
        if(ql <= mid) upd(ls, l, mid, ql, qr, v);
        if(qr > mid) upd(rs, mid + 1, r, ql, qr, v);
        up(u);
    }
    inline ll ask(int u, int l, int r, int ql, int qr){
        if(l >= ql && r <= qr) return t[u].sum;
        int mid = (l + r) >> 1; ll res = 0; down(u);
        if(ql <= mid) res += ask(ls, l, mid, ql, qr);
        if(qr > mid) res += ask(rs, mid + 1, r, ql, qr);
        return res;
    }
    #undef ls 
    #undef rs
}
signed main(){
    cin.tie(nullptr) -> sync_with_stdio(false);
    cin >> n;
    for(int i=1;i<=n;i++) 
        cin >> a[i], pos[a[i]].emplace_back(i);
    for(int i=1;i<=n;i++) 
        T::upd(rt[i], rt[i - 1], 0, n, a[i], i);
    if(pos[0].empty()) return cout << 0, 0;
    for(int i=1;i<=n;i++)
        g[a[i] > 0 ? 0 : 1].emplace_back(mk(i, i));
    for(int i=1;i<=n;i++) {
        for(auto [L, R] : g[i - 1]) {
            int l = get_pre(L, i - 1), r = get_nxt(R, i - 1);
            if(l >= 1) 
                g[mex(l, R)].emplace_back(mk(l, R));
            if(r <= n) 
                g[mex(L, r)].emplace_back(mk(L, r));
        }
        stable_sort(g[i].begin(), g[i].end(), [&](pii p1, pii p2){
            return p1.fi == p2.fi ? p1.se < p2.se : p1.fi > p2.fi;
        });
        vector<pii>qwq; int lst = 1e9;
        for(auto v : g[i]) if(v.se < lst) lst = v.se, qwq.emplace_back(v);
        g[i].swap(qwq); 
    }
    // for(int i=0;i<=n;i++) {
    //  cerr << i << ": \n";
    //  for(auto [l, r] : g[i]) cerr << l << ' ' << r << '\n';
    // }
    for(int i=0;i<=n;i++) {
        for(auto [l, r] : g[i])
            add[r].emplace_back(mk(l, i));
    }
    SGT::build(1, 1, n); ll ans = 0;
    for(int i=1;i<=n;i++) {
        for(auto [l, w] : add[i]) 
            SGT::upd(1, 1, n, 1, l, w);
        ans += SGT::ask(1, 1, n, 1, i);
    } cout << ans;
    return 0;
}

:::