题解：CF2128D Sum of LDS
SkyWave
·
·
题解
简要题意
给定一个长度为 n 的排列 p_1, p_2, \ldots, p_n，并且对所有 1 \le i \le n-2 都满足 \max(p_i, p_{i+1}) > p_{i+2}。
请计算：对所有满足 1 \le l \le r \le n 的子数组 (p_l, p_{l+1}, \ldots, p_r)，其最长严格下降子序列（LDS）的长度之和。
思路
设 p_{n+1} = p_{n+2} = p_{n+3} = -\infty，\{i_1, \ldots, i_m\} 为所有满足 p_i > p_{i+1} 的 i \in [n] 组成的集合。
可以分两步证明，序列 (i_1, \ldots, i_m) 是 p 的一个 LDS。
它是单调递减的
设 k \in [m]。
情况 1：(i_k) + 1 = i_{k+1}
按照集合构造规则，直接有 p_{i_k} > p_{(i_k) + 1} = p_{i_{k+1}}。
情况 2：(i_k) + 1 < i_{k+1}
此时，根据题意，有 \max(p_{i_k}, p_{(i_k) + 1}) > p_{(i_k) + 2}。
别忘了，根据规则，现在不仅有 $p_{i_k} > p_{(i_k) + 2}$，还有 $p_{i_k} > p_{(i_k) + 1}$。根据题意，又有 $p_{i_k} > \max(p_{(i_k) + 1}, p_{(i_k) + 2}) > p_{(i_k) + 3)}$，于是就有了传递性，可以一路传出去了。
综上所述，$p_{i_k} > \max(p_{(i_k) + 1}, p_{(i_k) + 2}, \ldots, p_{n})$ 恒成立，单调性得证。
## 它是最长的
注意到，若 $p_i < p_{i + 1}$，那么 $i$ 与 $i + 1$ 至多只能选择其中一个存在于 LDS 中。
因此答案的上界为 $n - \sum_{i=1}^{n-1} \left[p_i < p_{i+1}\right]$，即 $n - (n - m) = m$，注意到 $|\{i_1, \ldots, i_m\}| = m$，正好达到上界，最优性得证。
---
综上所述，$(i_1, \ldots, i_m)$ 是 $p$ 的一个 LDS。
因此原问题被转换成了：计算 $\sum_{l=1}^{n} \sum_{r=l}^n 1 + \sum_{k=l}^{r-1} [p_k > p_{k+1}]$ 的值。
相信有良好普及组基础的同学，可以轻松地在 $\Theta(n)$ 的时空复杂度下解决此问题。
# 实现
```cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int N = 500000 + 1;
int a[N];
void solve() {
int n;
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
}
ll ans = 0;
for (int i = 1; i < n; ++i) if (a[i] > a[i + 1]) {
ans += (ll)i * (n - i);
}
cout << ans + ((ll)n * (n + 1) >> 1) << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
```
时空复杂度：均为 $\Theta(n)$。