A. LIS

题面

给一个数组

a_1, a_2, \dots, a_n

，定义

f(L, R)

的值为：

设当前索引为 $i := L$ ，答案为 $1$ 。
对于 $i < j \leq R$ ，选取最小的 $j$ ，满足 $a_j > a_i$ 。如果找不到 $j$ ，则结束程序。
让 $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

的和，即答案。

实现

CPP

#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)

。

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

文章操作