#P11786. 「FAOI-R4」说好的幸福呢
「FAOI-R4」说好的幸福呢
题目背景
UPD:数据已加强。
题目描述
小 M 有一个长度为 的排列 。
对于一个长度为 的序列 ,小 M 可以执行以下操作:
- 选择一个满足 的位置 ,将序列变为 $[b_i,b_{i+1},\cdots,b_{k},b_{1},b_{2},\cdots,b_{i-2},b_{i-1}]$。也就是说,将 的一个后缀移到开头。
定义序列 的价值 为「将 变成严格上升序列的最小操作数」。若无法通过操作变成严格上升序列,则 。
你需要求出 $\sum\limits_{l=1}^{n}\sum\limits_{r=l}^{n}f([a_{l},a_{l+1},\cdots,a_{r-1},a_{r}])$,即 中所有子串的价值之和。
输入格式
第一行一个正整数 表示测试数据组数。
对于每组数据:
- 第一行输入一个正整数 ,表示排列长度。
- 第二行输入一个长度为 的排列 。
输出格式
输出共 行,第 行一个整数表示第 组测试数据的答案。
12
1
1
2
1 2
2
2 1
3
1 2 3
3
1 3 2
3
2 1 3
3
2 3 1
3
3 1 2
3
3 2 1
6
1 2 5 6 3 4
9
9 8 7 6 5 4 3 2 1
12
1 2 3 4 5 6 7 8 9 10 11 12
0
0
1
0
1
1
2
2
2
4
8
0
提示
【样例解释】
对于第三组样例:区间 已经是严格上升序列,不需要操作。而对于区间 ,选择 即可将其变为严格上升序列。故答案为 。
对于第六组样例:区间 可以通过一次 的操作变为严格上升序列,而对于区间 ,可以证明无论如何操作都无法将其排序。
【数据范围与约定】
本题开启子任务捆绑测试。
- Subtask 1(15 pts):,。
- Subtask 2(35 pts):,。
- Subtask 3(30 pts):,。
- Subtask 4(20 pts):无特殊限制。
对于所有数据,保证 ,,。
【提示】
本题输入量略大,你可以在程序的开头加上 std::cin.tie(0)->sync_with_stdio(0)
,并使用 std::cin
来读入,保证可以在 600ms 内读入所有数据。可以参考以下程序:
#include <bits/stdc++.h>
using namespace std;
const int N = 5e6 + 1;
long long T, n, ans, a[N];
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> T;
while (T --) {
cin >> n;
for (int i = 1; i <= n; i ++)
cin >> a[i];
// compute the answer
cout << ans << '\n';
}
return 0;
}