Range Sorting solution codeforces
The only difference between this problem and the hard version is the constraints on 𝑡� and 𝑛�.
You are given an array 𝑎�, consisting of 𝑛� distinct integers 𝑎1,𝑎2,…,𝑎𝑛�1,�2,…,��.
Define the beauty of an array 𝑝1,𝑝2,…𝑝𝑘�1,�2,…�� 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 𝑙� and 𝑟� (1≤𝑙<𝑟≤𝑘1≤�<�≤�).
- Sort the subarray 𝑝𝑙,𝑝𝑙+1,…,𝑝𝑟��,��+1,…,�� in 𝑟−𝑙�−� seconds.
Please calculate the sum of beauty over all subarrays of array 𝑎�.
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 𝑡� (1≤𝑡≤5⋅1031≤�≤5⋅103). The description of the test cases follows.
The first line of each test case contains a single integer 𝑛� (1≤𝑛≤5⋅1031≤�≤5⋅103) — the length of the array 𝑎�.
The second line of each test case consists of 𝑛� integers 𝑎1,𝑎2,…,𝑎𝑛�1,�2,…,�� (1≤𝑎𝑖≤1091≤��≤109). It is guaranteed that all elements of 𝑎� are pairwise distinct.
It is guaranteed that the sum of 𝑛� over all test cases does not exceed 5⋅1035⋅103.
Range Sorting solution codeforces
For each test case, output the sum of beauty over all subarrays of array 𝑎�.
input
output
1 2 8 16 232
In the first test case:
- The subarray [6][6] is already sorted, so its beauty is 00.
- The subarray [4][4] is already sorted, so its beauty is 00.
- You can sort the subarray [6,4][6,4] in one operation by choosing 𝑙=1�=1 and 𝑟=2�=2. Its beauty is equal to 11.
The sum of beauty over all subarrays of the given array is equal to 0+0+1=10+0+1=1.In the second test case:
- The subarray [3][3] is already sorted, so its beauty is 00.
- The subarray [10][10] is already sorted, so its beauty is 00.
- The subarray [6][6] is already sorted, so its beauty is 00.
- The subarray [3,10][3,10] is already sorted, so its beauty is 00.
- You can sort the subarray [10,6][10,6] in one operation by choosing 𝑙=1�=1 and 𝑟=2�=2. Its beauty is equal to 2−1=12−1=1.
- You can sort the subarray [3,10,6][3,10,6] in one operation by choosing 𝑙=2�=2 and 𝑟=3�=3. Its beauty is equal to 3−2=13−2=1.
The sum of beauty over all subarrays of the given array is equal to 0+0+0+0+1+1=20+0+0+0+1+1=2.