Range Sorting (Easy Version)
题面翻译
对一个数组 \(\{p_i\}\) 的一段区间 \([l,r]\) 排序的代价为 \(r-l\) ，对整个数组 \(p_i\) 排序的代价为选定若干区间并排序，使得整个数组有序的代价之和。
求 \(\{a_i\}\) 的所有子段排序的代价之和。
题目描述
The only difference between this problem and the hard version is the constraints on $ t $ and $ n $ .
You are given an array $ a $ , consisting of $ n $ distinct integers $ a_1, a_2, \ldots, a_n $ .
Define the beauty of an array $ p_1, p_2, \ldots p_k $ as the minimum amount of time needed to sort this array using an arbitrary number of range-sort operations. In each range-sort operation, you will do the following:
- Choose two integers $ l $ and $ r $ ( $ 1 \le l < r \le k $ ).
- Sort the subarray $ p_l, p_{l + 1}, \ldots, p_r $ in $ r - l $ seconds.
Please calculate the sum of beauty over all subarrays of array $ a $ .
A subarray of an array is defined as a sequence of consecutive elements of the array.
输入格式
Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 5 \cdot 10^3 $ ). The description of the test cases follows.
The first line of each test case contains a single integer $ n $ ( $ 1 \le n \le 5 \cdot 10^3 $ ) — the length of the array $ a $ .
The second line of each test case consists of $ n $ integers $ a_1,a_2,\ldots, a_n $ ( $ 1\le a_i\le 10^9 $ ). It is guaranteed that all elements of $ a $ are pairwise distinct.
It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 5 \cdot 10^3 $ .
输出格式
For each test case, output the sum of beauty over all subarrays of array $ a $ .
样例 #1
样例输入 #1
5
2
6 4
3
3 10 6
4
4 8 7 2
5
9 8 2 4 6
12
2 6 13 3 15 5 10 8 16 9 11 18
样例输出 #1
1
2
8
16
232
提示
In the first test case:
- The subarray $ [6] $ is already sorted, so its beauty is $ 0 $ .
- The subarray $ [4] $ is already sorted, so its beauty is $ 0 $ .
- You can sort the subarray $ [6, 4] $ in one operation by choosing $ l = 1 $ and $ r = 2 $ . Its beauty is equal to $ 1 $ .
The sum of beauty over all subarrays of the given array is equal to $ 0 + 0 + 1 = 1 $ .In the second test case:
- The subarray $ [3] $ is already sorted, so its beauty is $ 0 $ .
- The subarray $ [10] $ is already sorted, so its beauty is $ 0 $ .
- The subarray $ [6] $ is already sorted, so its beauty is $ 0 $ .
- The subarray $ [3, 10] $ is already sorted, so its beauty is $ 0 $ .
- You can sort the subarray $ [10, 6] $ in one operation by choosing $ l = 1 $ and $ r = 2 $ . Its beauty is equal to $ 2 - 1 = 1 $ .
- You can sort the subarray $ [3, 10, 6] $ in one operation by choosing $ l = 2 $ and $ r = 3 $ . Its beauty is equal to $ 3 - 2 = 1 $ .
The sum of beauty over all subarrays of the given array is equal to $ 0 + 0 + 0 + 0 + 1 + 1 = 2 $ .
分析
给我们一个数组 \(a\) 要求我们求出对 \(a\) 所有子区间排序所需要的最小花费
我们可以总结出两个规律：
- 每次选择的一定是不交区间
比如我们要对区间 \([l, r]\) 排序，选 \([l, l + k]\) 和 \([l + k - 1, r]\) 的花费一定比直接选择 \([l, r]\) 排序来的要大 - 独立的处理每个不交子区间不劣于处理整个大区间
\(cost(l, r) = cost(l, l + k) + cost(l + k + 1, r) + 1\)
对于 \([l ,r]\) 如果存在 \(k\) 可以把区间分成两段排序，那么就有左区间最大值小于右区间最小值的性质，即 \(Max_{左} < Min_{右}\)
但是如果遍历每一个区间，找到每个区间内的分界点太复杂了且会超时，所以我们遍历 \(i\) ，看 \(a[i]\) 可以成为哪些区间的划分点，同时为了方便操作我们根据大小把数组 \(a\) 内的元素映射成 \(1\) 到 \(n\) 方便后续操作且对答案没有影响
首先我们遍历 \(i\) 的右边，维护在区间 \([i + 1, k]\) 的最小值，并统计以这个值为最小值的 \(i\) 的右边的区间（以 \(i + 1\) 为起点）一共有多少个，等遍历完之后，我们可以以前缀和的方式计算出在 \(i\) 的右边，有多少个区间的最小值 \(\ge x\) ， 我们再遍历 \(i\) 的左边，找到左边每个区间 (以 \(i\) 为终点) 的最大值x，这样就找到了满足 \(Max_{左} < Min_{右}\) 的可以用 \(a[i]\) 划分的区间了
记得答案要用 long long 存，不然会溢出
代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 5e3 + 10;
typedef long long ll;
int b[N];
struct A
{
int v, id;
}a[N];
bool cmp(A p, A q)
{
return p.v < q.v;
}
int main()
{
int t;
scanf("%d", &t);
while (t--)
{
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i].v);
a[i].id = i;
}
sort(a + 1, a + n + 1, cmp); //要从下标为1开始排
//按排序映射成1~n 方便处理
for (int i = 1; i <= n; i++)
{
//要放在本来的位置
b[a[i].id] = i;
}
//最大代价就是每一个子区间都要排序
ll mc = 0;
for (int i = 1; i < n; i++) mc += i * (n - i);
//枚举每一个可以断开的点
for (int i = 1; i < n; i++)
{
int sum[N] = { 0 };
//找出以 i + 1 为起始的区间内的最小值 并记录有几段区间的最小值是这个数
int minv = 1e9;
for (int j = i + 1; j <= n; j++)
{
minv = min(minv, b[j]);
sum[minv]++; //这里sum[q]表示以q为最小值的区间个数
}
for (int j = n; j >= 1; j--)
{
sum[j] += sum[j + 1]; //这里sum[q]表示最小值大于等于q的区间个数 类似前缀和方式
}
int maxv = 0;
for (int j = i; j > 0; j--)
{
maxv = max(maxv, b[j]);
mc -= sum[maxv + 1]; //b内只有 1~n 且没有重复元素
}
}
printf(" %lld\n", mc);
}
}