ABC470G

ssy666666 · 2026-08-09 09:45:03 · 题解

这个扫描线感觉挺板的吧。

一些定义

定义 g(l,r) 为 A_l 到 A_r 之间最小的未出现的自然数。

定义 nxt_i 表示离 i 最近的数，使得 A_i=A_{nxt_i}。

正确解法

这种对于所有区间统计的，大部分都可以往扫描线去靠。

先预处理出 g(1,i)，这个可以随便用一个并查集维护一下，然后考虑从 g(l,r) 怎么转移到 g(l+1,r)。

这其实就是删掉了最开头的一个元素。实际上，我们要考虑的就是这个元素的贡献。

对于 g(l+1,r),r \ge nxt_l 的部分显然没有影响，因为数集显然相同，但是在 [l+1,nxt_l) 的部分，会缺少 A_l 这个自然数，可能导致答案减小。

那具体的，对于哪些 r \in [l+1,nxt_l) 会导致减小呢？显然是 g(l,r) > A_l 的部分，因为这部分中，最小的自然数不是 A_l，而现在 A_l 这个数不存在了，那么新的 g(l+1,r) 就应该等于 A_l。

那做法就很明了了，其实我们刚才说的就相当于对 r \in [l+1,nxt_l) 的部分进行区间对 A_l 取最小值的操作，然后要查询全局和。我承认你可以吉司机线段树直接做，但是还有更简单的做法。

注意到 g(l,r) \le g(l,r+1)，因此实际上我们可以通过线段树二分第一个 r 使得 g(l,r) > A_l，这样，就变成了区间覆盖，区间求和。时间复杂度 O(n \log n)。实现起来并没有太多的细节。

AC Code

#include<bits/stdc++.h>
#define int long long
using namespace std ;
const int MAXN = 3e5 + 7 ;
int a[MAXN] ;
int val[MAXN] ;
struct SegmentTree {
    int mx[4 * MAXN] ;
    int sum[4 * MAXN] ;
    int lan[4 * MAXN] ;

    void push_up(int u) {
        mx[u] = max(mx[u * 2] , mx[u * 2 + 1]) ;
        sum[u] = sum[u * 2] + sum[u * 2 + 1] ;
    }

    void BuildTree(int u , int l , int r) {
        lan[u] = -1 ;
        if (l == r) {
            mx[u] = sum[u] = val[l] ;
            return ;
        }
        int mid = (l + r) >> 1 ;
        BuildTree(u * 2 , l , mid) ;
        BuildTree(u * 2 + 1 , mid + 1 , r) ;
        push_up(u) ;
    }

    void push_down(int u , int l , int r) {
        if (lan[u] == -1)   return ;
        int mid = (l + r) >> 1 ;
        lan[u * 2] = lan[u * 2 + 1] = mx[u * 2] = mx[u * 2 + 1] = lan[u] ;
        sum[u * 2] = lan[u] * (mid - l + 1) ;
        sum[u * 2 + 1] = lan[u] * (r - mid) ;
        lan[u] = -1 ;
        return ;
    }

    int Binary(int u , int l , int r , int val) {
        if (l == r) return l ;

        push_down(u , l , r) ;
        int mid = (l + r) >> 1 ;
        if (mx[u * 2] >= val) {
            return Binary(u * 2 , l , mid , val) ;
        }
        else {
            return Binary(u * 2 + 1 , mid + 1 , r , val) ;
        }
    }

    void Change(int u , int l , int r , int gl , int gr , int val) {
        if (gl <= l and r <= gr) {
            lan[u] = mx[u] = val ;
            sum[u] = val * (r - l + 1) ;
            return ;
        }

        push_down(u , l , r) ;
        int mid = (l + r) >> 1 ;
        if (mid >= gl)  Change(u * 2 , l , mid , gl , gr , val) ;
        if (mid + 1 <= gr)  Change(u * 2 + 1 , mid + 1 , r , gl , gr , val) ;
        push_up(u) ;
        return ;
    }

    int Query(int u , int l , int r , int gl , int gr) {
        if (gl <= l and r <= gr) {
            return sum[u] ;
        }

        push_down(u , l , r) ;
        int mid = (l + r) >> 1 ;
        int ans = 0 ;
        if (mid >= gl)  ans += Query(u * 2 , l , mid , gl , gr) ;
        if (mid + 1 <= gr)  ans += Query(u * 2 + 1 , mid + 1 , r , gl , gr) ;
        return ans ;
    }
}g;

struct DSU {
    int fa[MAXN] ;

    void Init(int n) {
        for (int i = 0 ; i <= n + 1 ; i ++) {
            fa[i] = i ;
        }
    }

    int get_fa(int u) {
        if (fa[u] == u) return u ;
        return fa[u] = get_fa(fa[u]) ;
    }

    void merge(int u , int v) {
        int Fau = get_fa(u) , Fav = get_fa(v) ;
        if (Fau == Fav) return ;
        fa[Fau] = Fav ;
        return ;
    }
}o;

int nxt[MAXN] ;
int lst[MAXN] ;
signed main()
{
//  freopen("" , "r" , stdin) ;
//  freopen("" , "w" , stdout) ;

    ios::sync_with_stdio(0) ;
    cin.tie(0) ;
    cout.tie(0) ;

    int n ;
    cin >> n ;
    o.Init(n) ;
    for (int i = 1 ; i <= n ; i ++) {
        cin >> a[i] ;
        if (lst[a[i]] != 0) {
            nxt[lst[a[i]]] = i ;
        }
        lst[a[i]] = i ;
        o.merge(a[i] , a[i] + 1) ;
        val[i] = o.get_fa(0) ;
    }

    for (int i = 1 ; i <= n ; i ++) {
        if (!nxt[i]) {
            nxt[i] = n + 1 ;
        }
    }

    g.BuildTree(1 , 1 , n) ;

    int ans = 0 ;
    for (int i = 1 ; i <= n ; i ++) {
        ans += g.Query(1 , 1 , n , i , n) ;

        int dir = g.Binary(1 , 1 , n , a[i] + 1) ;
        int val = g.Query(1 , 1 , n , dir , dir) ;
        if (val > a[i])
            g.Change(1 , 1 , n , dir , nxt[i] - 1 , a[i]) ;
    }

    cout << ans ;

    return 0 ;
}