简要题意
给定一个长度为
n 的排列
p1,p2,…,pn，并且对所有
1≤i≤n−2 都满足
max(pi,pi+1)>pi+2。
请计算：对所有满足
1≤l≤r≤n 的子数组
(pl,pl+1,…,pr)，其
最长严格下降子序列（LDS）的长度之和。
思路
设
pn+1=pn+2=pn+3=−∞，
{i1,…,im} 为所有满足
pi>pi+1 的
i∈[n] 组成的集合。
可以分两步证明，序列
(i1,…,im) 是
p 的一个 LDS。
它是单调递减的
情况 1：(ik)+1=ik+1
按照集合构造规则，直接有
pik>p(ik)+1=pik+1。
情况 2：(ik)+1<ik+1
此时，根据题意，有
max(pik,p(ik)+1)>p(ik)+2。
(ik)+1<ik+1，说明
(ik)+1 没有被选入集合，又说明
p(ik)+1<p(ik)+2，所以
pik>p(ik)+2 只能成立，否则
max(pik,p(ik)+1)>p(ik)+2 不成立。
别忘了，根据规则，现在不仅有
pik>p(ik)+2，还有
pik>p(ik)+1。根据题意，又有
pik>max(p(ik)+1,p(ik)+2)>p(ik)+3)，于是就有了传递性，可以一路传出去了。
综上所述，
pik>max(p(ik)+1,p(ik)+2,…,pn) 恒成立，单调性得证。
它是最长的
注意到，若
pi<pi+1，那么
i 与
i+1 至多只能选择其中一个存在于 LDS 中。
因此答案的上界为
n−∑i=1n−1[pi<pi+1]，即
n−(n−m)=m，注意到
∣{i1,…,im}∣=m，正好达到上界，最优性得证。
综上所述，
(i1,…,im) 是
p 的一个 LDS。
因此原问题被转换成了：计算
∑l=1n∑r=ln1+∑k=lr−1[pk>pk+1] 的值。
相信有良好普及组基础的同学，可以轻松地在
Θ(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;
}
时空复杂度：均为
Θ(n)。