题解：AT_abc470_g [ABC470G] ΣШX

xz001 · 2026-08-10 18:04:29 · 题解

我们考虑计算对于 i\in [0,n-1]，mex>i 的区间数量，显然其和就是答案。

我们发现包含每个点的区间都是一个 x\in [1,i],y\in [i,n] 的矩阵，我们可以每次把 a_x=i 的区间加入，被目前所有 i 的矩阵包含过的点所代表的区间就是合法的，注意到这些区间都是贴着右上角的，因此我们可以考虑维护对于每个 y 维护目前覆盖到它的最小的 x，问题就变成了区间取 \min，全局和，吉斯机线段树即可。

#include <bits/stdc++.h>

#define int long long
#define ls(x) ((x) << 1)
#define rs(x) ((x) << 1 | 1)

using namespace std;

const int N = 5e5 + 5;

int n, m, a[N];

struct mat {
    int a00, a01, a11;
    inline void mul (const mat &b) {
        a01 = max(a00 + b.a01, a01 + b.a11);
        a00 += b.a00;
        a11 += b.a11;
        return;
    }
    inline void Mul (const mat &b) {
        a01 = max(a00 + b.a01, a01 + b.a11);
        a00 += b.a00;
        return;
    }
};

struct node {
    int l, r, m1, m2, cnt, add1, add2;
    int sum;
    mat a, add, tag;
    bool f1, f2;
};

node t[4 * N];

inline void push_up (const int p) {
    t[p].sum = t[ls(p)].sum + t[rs(p)].sum;
    t[p].m1 = max(t[ls(p)].m1, t[rs(p)].m1);
    t[p].m2 = max(t[ls(p)].m2, t[rs(p)].m2);
    if (t[p].m1 != t[ls(p)].m1) t[p].m2 = max(t[p].m2, t[ls(p)].m1);
    if (t[p].m1 != t[rs(p)].m1) t[p].m2 = max(t[p].m2, t[rs(p)].m1);
    t[p].cnt = 0;
    if (t[p].m1 == t[ls(p)].m1) t[p].cnt += t[ls(p)].cnt;
    if (t[p].m1 == t[rs(p)].m1) t[p].cnt += t[rs(p)].cnt;
    t[p].a.a00 = max(t[ls(p)].a.a00, t[rs(p)].a.a00);
    t[p].a.a01 = max(t[ls(p)].a.a01, t[rs(p)].a.a01); 
    return;
}

inline void build (const int l, const int r, const int p) {
    t[p].l = l, t[p].r = r;
    if (l == r) {
        t[p].sum = t[p].m1 = 1e9;
        t[p].m2 = -2e9;
        t[p].cnt = 1;
        t[p].a.a00 = t[p].a.a01 = 1e9;
        t[p].a.a11 = -2e9;
        return;
    }
    const int mid = (l + r) >> 1;
    build (l, mid, ls(p));
    build (mid + 1, r, rs(p));
    push_up(p);
    return; 
}

inline void lazy_tag1 (const int p, const int d) {
    t[p].sum += 1ll * (t[p].r - t[p].l + 1) * d;
    t[p].m1  += d;
    t[p].m2  += d;
    t[p].add1 += d;
    return;
} 

inline void lazy_tag2 (const int p, const int d) {
    t[p].sum += 1ll * t[p].cnt * d;
    t[p].m1  += d;
    t[p].add2 += d;
    return;
}

inline void lazy_tag3 (const int p, const mat &now) {
    if (t[p].f1) t[p].add.mul(now);
    else t[p].add = now, t[p].f1 = true;
    return;
}

inline void lazy_tag4 (const int p, const mat &now) {
    if (t[p].f2) t[p].tag.mul(now);
    else t[p].tag = now, t[p].f2 = true;
    return;
}

inline void push_down (const int p) {
    if (t[p].add1) {
        lazy_tag1 (ls(p), t[p].add1);
        lazy_tag1 (rs(p), t[p].add1);
        t[p].add1 = 0;
    }
    const int mx = max(t[ls(p)].m1, t[rs(p)].m1);
    if (t[ls(p)].m1 == mx) {
        if (t[p].f1) {
            t[ls(p)].a.Mul(t[p].add); 
            lazy_tag3 (ls(p), t[p].add);
            if (t[p].f2) {
                lazy_tag4 (ls(p), t[p].tag);
            }
        } else if (t[p].f2) {
            lazy_tag4 (ls(p), t[p].tag);
        }
    } else {
        if (t[p].f2) {
            t[ls(p)].a.Mul(t[p].tag); 
            lazy_tag3 (ls(p), t[p].tag);
            lazy_tag4 (ls(p), t[p].tag);
        }
    }
    if (t[rs(p)].m1 == mx) {
        if (t[p].f1) {
            t[rs(p)].a.Mul(t[p].add); 
            lazy_tag3 (rs(p), t[p].add);
            if (t[p].f2) {
                lazy_tag4 (rs(p), t[p].tag);
            }
        } else if (t[p].f2) {
            lazy_tag4 (rs(p), t[p].tag);
        }
    } else {
        if (t[p].f2) {
            t[rs(p)].a.Mul(t[p].tag); 
            lazy_tag3 (rs(p), t[p].tag);
            lazy_tag4 (rs(p), t[p].tag);
        }
    }
    t[p].f1 = t[p].f2 = false;
    if (t[p].add2) {
        if (t[ls(p)].m1 == mx) lazy_tag2 (ls(p), t[p].add2);
        if (t[rs(p)].m1 == mx) lazy_tag2 (rs(p), t[p].add2);
        t[p].add2 = 0; 
    } 
    return;
}

inline void update (const int l, const int r, const int p, const int d) {
    if (l <= t[p].l && t[p].r <= r) {
        mat now;
        now.a00 = now.a01 = d;
        now.a11 = 0;
        t[p].a.Mul(now);
        lazy_tag3 (p, now); 
        lazy_tag4 (p, now);
        lazy_tag1 (p, d);
        return;
    }
    push_down(p);
    const int mid = (t[p].l + t[p].r) >> 1;
    if (l <= mid) update (l, r, ls(p), d);
    if (r >  mid) update (l, r, rs(p), d);
    push_up(p);
    return; 
}

inline void modify (const int l, const int r, const int p, const int d) {
    if (t[p].m1 <= d) return;
    if (l <= t[p].l && t[p].r <= r && t[p].m2 < d) {
        mat now;
        now.a00 = now.a01 = d - t[p].m1;
        now.a11 = 0;
        t[p].a.Mul(now);
        lazy_tag3 (p, now); 
        lazy_tag2 (p, d - t[p].m1);
        return;
    }
    push_down(p);
    const int mid = (t[p].l + t[p].r) >> 1;
    if (l <= mid) modify (l, r, ls(p), d);
    if (r >  mid) modify (l, r, rs(p), d);
    push_up(p);
    return; 
}

inline int query1 (const int l, const int r, const int p) {
    if (l <= t[p].l && t[p].r <= r) return t[p].sum;
    push_down(p);
    const int mid = (t[p].l + t[p].r) >> 1;
    if (l <= mid && r > mid) return query1 (l, r, ls(p)) + query1 (l, r, rs(p));
    if (l <= mid) return query1 (l, r, ls(p));
    return query1 (l, r, rs(p));
}

inline int query2 (const int l, const int r, const int p) {
    if (l <= t[p].l && t[p].r <= r) return t[p].m1;
    push_down(p);
    const int mid = (t[p].l + t[p].r) >> 1;
    if (l <= mid && r > mid) return max(query2 (l, r, ls(p)), query2 (l, r, rs(p)));
    if (l <= mid) return query2 (l, r, ls(p));
    return query2 (l, r, rs(p));
}

inline int query3 (const int l, const int r, const int p) {
    if (l <= t[p].l && t[p].r <= r) return t[p].a.a01;
    push_down(p);
    const int mid = (t[p].l + t[p].r) >> 1;
    if (l <= mid && r > mid) return max(query3 (l, r, ls(p)), query3 (l, r, rs(p)));
    if (l <= mid) return query3 (l, r, ls(p));
    return query3 (l, r, rs(p));
}

vector <int> g[N];

signed main() {
    ios :: sync_with_stdio(0), cin.tie(0), cout.tie(0);

    cin >> n;
    for (int i = 1; i <= n; ++ i ) cin >> a[i], g[a[i]].push_back(i);
    build(1, n, 1);
    int res = 0;
    for (int i = 0; i < n; ++ i ) {
        if (!g[i].size()) break;
        g[i].push_back(n + 1);
        if (g[i][0] > 1) {
            modify(1, g[i][0] - 1, 1, 0);
        //  cout << 1 << ' ' << g[i][0] - 1 << endl;
        } 
        for (int j = 0; j + 1 < (int)g[i].size(); ++ j ) {
            int l = g[i][j], r = g[i][j + 1] - 1;
            modify(l, r, 1, l);
        //  cout << l << ' ' << r << endl;
        }//cout << endl;
        //cout << t[1].sum << endl; 
        res += t[1].sum;
    }
    cout << res << '\n';

    return 0; 
}