2025 超新星战队 B 队暑假集训模拟赛 day1

· · 个人记录

A. LIS

题面

给一个数组 a_1, a_2, \dots, a_n ，定义 f(L, R) 的值为：

  1. 设当前索引为 i := L ，答案为 1 。

  2. 对于 i < j \leq R ，选取最小的 j ，满足 a_j > a_i 。如果找不到 j ，则结束程序。

  3. 让 i := j ，并将答案增加 1 。然后跳转到步骤 2。

求 \sum_{L=1}^{n} \sum_{R=L}^{n} f(L, R)

输入格式

第一行包含一个整数 T ，表示 T 组测试数据。

对于每组测试数据：

第一行包含一个整数 n 。

接下来一行包含 n 个整数 a_1, a_2, \dots, a_n 。

输出格式

对于每组测试数据，输出一行包含一个整数，表示答案。

数据范围

对于所有数据，保证 1 \leq T,n,\sum n \leq 4 \cdot 10^5, 1 \leq a_i \leq n。

思路

先固定 l。套路地，设 \#(\ge i) 为 \sum_{r=l}^n \left|f(l, r) \ge i\right|，则有 \sum_{r=l}^n f(l, r) = \sum_{i=1}^{n} \#(\ge i)。

设 \text{nge}_i 为满足 i < j \leq n \land a_i < a_j 的最小的 j，若不存在这样的 j，则设 \text{nge}_i = n + 1。

设 r(i) = n - i + 1。注意到 \#(\ge 1) = r_l，\#(\ge 2) = r(\text{nge}_l)，同理可得 \#(\ge 3) = r(\text{nge}_{\text{nge}_l})，\#(\ge 4) = r(\text{nge}_{\text{nge}_{\text{nge}_l}})……

设 u \in [n]。因为有 u < \text{nge}(u)，所以如果将 u \gets nge_u 视作 g 的一条有向边，那么 g 就是一张以 n+1 为根的树。

设 s_u 为所有点 v 的 r(v) 之和，满足 v 在 u 到 n+1 的简单路径上。容易在 \Theta(n) 时间计算出 s 的和，即答案。

实现

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

using ll = long long;

constexpr int N = 400000 + 1;

int a[N + 1], stk[N + 1], f[N + 1];

void solve() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    a[n + 1] = 1 << 30;
    f[n + 1] = 0;
    int top = 1;
    stk[top] = n + 1;
    for (int i = n; i; --i) {
        while (top && a[stk[top]] <= a[i]) {
            --top;
        }
        f[i] = n - i + 1 + f[stk[top]];
        stk[++top] = i;
    }
    cout << accumulate(f + 1, f + n + 1, 0ll) << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

时空复杂度：均为 \Theta(n)。