I Hate ARC

Tomwsc · 2026-08-10 15:34:03 · 题解

arc 太难了。abc 真简单。

从左往右扫描线，用一棵权值线段树维护每种数最后出现的位置。

考虑扫到点 i 时的答案。如果 [j, i] 这段区间答案为 k，则说明 [0, k) 中的数在线段树上的值均 \ge j 且 k 在线段树上的值 <j。

我们设线段树维护的每个数 i 出现的最后位置为 p_i。则 p 中有贡献的值的一定形如单调递减子序列。对于 i 的贡献，记 j<i,p_j>p_i 且 \forall k\in(j, i),p_k>p_j，那么显然 i 对答案的贡献便是 i\times (p_j-p_i)。

考虑到需要维护的东西是单调递减序列。于是直接楼房重建即可。

时间复杂度两只老哥。

::::success[Code]

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

using ll = long long;
using ld = long double;
using ull = unsigned long long;
using uint = unsigned int;
using i128 = __int128;

using PII = pair<int, int>;
using PLL = pair<ll, ll>;

#define fi first
#define se second

#define rep(i, j, k) for (int i = (j); i < (k); i++)
#define rrep(i, j, k) for (int i = (j); i > (k); i--)
#define _rep(i, j, k, l) for (int i = (j); i < k; i += l)
#define _rrep(i, j, k, l) for (int i = (j); i > k; i -= l)
#define __rep(i, j, k) for (int i = (j); i <= (k); i++)
#define __rrep(i, j, k) for (int i = (j); i >= (k); i--)
#define ___rep(i, j, k, l) for (int i = (j); i <= k; i += l)
#define ___rrep(i, j, k, l) for (int i = (j); i >= k; i -= l) 

constexpr ll inf = (1ll << 62);
constexpr int N = 3e5 + 10;

template <typename T> void chkmax(T& a, T b) { a = max(a, b); }
template <typename T> void chkmin(T& a, T b) { a = min(a, b); }

int n, a[N], minn[N << 2];
ll tree[N << 2];

ll calc(int l, int r, int k, int p) {
    if (minn[p] >= k) return 0ll;
    if (l == r) return 1ll * l * (k - minn[p]);
    int mid = l + r >> 1;
    if (minn[p << 1] < k) return calc(l, mid, k, p << 1) + tree[p] - tree[p << 1];
    return calc(mid + 1, r, k, p << 1 | 1);
}

void pushup(int l, int r, int p) {
    int mid = l + r >> 1;
    minn[p] = min(minn[p << 1], minn[p << 1 | 1]);
    tree[p] = tree[p << 1] + calc(mid + 1, r, minn[p << 1], p << 1 | 1);
}

void build(int l, int r, int p) {
    if (l == r) {
        minn[p] = -1;
        return;
    }
    int mid = l + r >> 1;
    build(l, mid, p << 1);
    build(mid + 1, r, p << 1 | 1);
    pushup(l, r, p);
}

void update(int l, int r, int x, int k, int p) {
    if (l == r) {
        tree[p] = 0;
        minn[p] = k;
        return;
    }
    int mid = l + r >> 1;
    if (x <= mid) update(l, mid, x, k, p << 1);
    else update(mid + 1, r, x, k, p << 1 | 1);
    pushup(l, r, p);
}

void solve() {
    cin >> n;
    rep(i, 0, n) {
        cin >> a[i];
    }
    build(0, n, 1);
    ll ans = 0;
    rep(i, 0, n) {
        if (a[i] <= n) {
            update(0, n, a[i], i, 1);
        }
        ans += tree[1];
    }
    cout << ans << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

::::