310399: CF1827F. Copium Permutation
Description
You are given a permutation $a_1,a_2,\ldots,a_n$ of the first $n$ positive integers. A subarray $[l,r]$ is called copium if we can rearrange it so that it becomes a sequence of consecutive integers, or more formally, if $$\max(a_l,a_{l+1},\ldots,a_r)-\min(a_l,a_{l+1},\ldots,a_r)=r-l$$ For each $k$ in the range $[0,n]$, print out the maximum number of copium subarrays of $a$ over all ways of rearranging the last $n-k$ elements of $a$.
InputEach test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.
The first line of each test case contains a single integer $n$ ($1\le n\le 2\cdot 10^5$).
The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$). It is guaranteed that the given numbers form a permutation of length $n$.
It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$.
OutputFor each test case print $n+1$ integers as the answers for each $k$ in the range $[0,n]$.
ExampleInput5 5 5 2 1 4 3 4 2 1 4 3 1 1 8 7 5 8 1 4 2 6 3 10 1 4 5 3 7 8 9 2 10 6Output
15 15 11 10 9 9 10 8 8 7 7 1 1 36 30 25 19 15 13 12 9 9 55 55 41 35 35 25 22 22 19 17 17Note
In the first test case, the answer permutations for each $k$ are $[1,2,3,4,5]$, $[5,4,3,2,1]$, $[5,2,3,4,1]$, $[5,2,1,3,4]$, $[5,2,1,4,3]$, $[5,2,1,4,3]$.
In the second test case, the answer permutations for each $k$ are $[1,2,3,4]$, $[2,1,3,4]$, $[2,1,3,4]$, $[2,1,4,3]$, $[2,1,4,3]$.
Input
题意翻译
对于一个排列 $\{a_i\}$，定义它的一个区间 $[l,r]$ 为 Copium 的当且仅当： $$ \max(a_l,a_{l+1},\ldots,a_r)-\min(a_l,a_{l+1},\ldots,a_r)=r-l $$ 给定排列 $\{a_i\}$，对于所有的 $k\in[0,n]\cap\mathbb Z$，求出把 $\{a_i\}$ 的后 $n-k$ 个数重排后这个排列的 Copium 区间数量最大值。Output
给定一个由前n个正整数组成的排列a_1, a_2, …, a_n。如果子数组[l, r]可以重新排列成一个连续整数序列，则称其为“copium”。更正式地说，如果max(a_l, a_{l+1}, …, a_r) - min(a_l, a_{l+1}, …, a_r) = r - l，则称其为“copium”。对于每个k在[0, n]范围内，打印出通过重新排列a的最后n-k个元素可以得到的所有“copium”子数组的最大数量。
输入数据格式：
每个测试包含多个测试用例。第一行包含测试用例数t（1 ≤ t ≤ 10^4）。接下来是每个测试用例的描述。
每个测试用例的第一行包含一个整数n（1 ≤ n ≤ 2·10^5）。
每个测试用例的第二行包含n个整数a_1, a_2, …, a_n（1 ≤ a_i ≤ n）。保证给定的数字构成一个长度为n的排列。
保证所有测试用例的n之和不超过2·10^5。
输出数据格式：
对于每个测试用例，打印n+1个整数，作为k在[0, n]范围内每个答案。
示例：
输入：
5
5
5 2 1 4 3
4
2 1 4 3
1
1
8
7 5 8 1 4 2 6 3
10
1 4 5 3 7 8 9 2 10 6
输出：
15 15 11 10 9 9
10 8 8 7 7
1 1
36 30 25 19 15 13 12 9 9
55 55 41 35 35 25 22 22 19 17 17
注意：
在第一个测试案例中，每个k的答案排列是[1,2,3,4,5]、[5,4,3,2,1]、[5,2,3,4,1]、[5,2,1,3,4]、[5,2,1,4,3]、[5,2,1,4,3]。
在第二个测试案例中，每个k的答案排列是[1,2,3,4]、[2,1,3,4]、[2,1,3,4]、[2,1,4,3]、[2,1,4,3]。题目大意： 给定一个由前n个正整数组成的排列a_1, a_2, …, a_n。如果子数组[l, r]可以重新排列成一个连续整数序列，则称其为“copium”。更正式地说，如果max(a_l, a_{l+1}, …, a_r) - min(a_l, a_{l+1}, …, a_r) = r - l，则称其为“copium”。对于每个k在[0, n]范围内，打印出通过重新排列a的最后n-k个元素可以得到的所有“copium”子数组的最大数量。 输入数据格式： 每个测试包含多个测试用例。第一行包含测试用例数t（1 ≤ t ≤ 10^4）。接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数n（1 ≤ n ≤ 2·10^5）。 每个测试用例的第二行包含n个整数a_1, a_2, …, a_n（1 ≤ a_i ≤ n）。保证给定的数字构成一个长度为n的排列。 保证所有测试用例的n之和不超过2·10^5。 输出数据格式： 对于每个测试用例，打印n+1个整数，作为k在[0, n]范围内每个答案。 示例： 输入： 5 5 5 2 1 4 3 4 2 1 4 3 1 1 8 7 5 8 1 4 2 6 3 10 1 4 5 3 7 8 9 2 10 6 输出： 15 15 11 10 9 9 10 8 8 7 7 1 1 36 30 25 19 15 13 12 9 9 55 55 41 35 35 25 22 22 19 17 17 注意： 在第一个测试案例中，每个k的答案排列是[1,2,3,4,5]、[5,4,3,2,1]、[5,2,3,4,1]、[5,2,1,3,4]、[5,2,1,4,3]、[5,2,1,4,3]。 在第二个测试案例中，每个k的答案排列是[1,2,3,4]、[2,1,3,4]、[2,1,3,4]、[2,1,4,3]、[2,1,4,3]。