You are given a permutation† a of length n . Find any permutation b of length n such that a1+b1≤a2+b2≤a3+b3≤…≤an+bn . It can be proven that a permutation b that satisfies the condition above always exists. † A permutation of length n is an array consisting of n distinct integers from 1 to n in arbitrary order. For example, [2,3,1,5,4] is a permutation, but [1,2,2] is not a permutation (2 appears twice in the array), and [1,3,4] is also not a permutation (n=3 but there is 4 in the array). Input Each test contains multiple test cases. The first line of input contains a single integer t (1≤t≤2000 ) — the number of test cases. The description of test cases follows. The first line of each test case contains a single integer n (1≤n≤100 ) — the length of permutations a and b . The second line of each test case contains n distinct integers a1,a2,…,an (1≤ai≤n ) — the elements of permutation a . All elements of a are distinct. Note that there is no bound on the sum of n over all test cases. Output For each test case, output any permutation b which satisfies the constraints mentioned in the statement. It can be proven that a permutation b that satisfies the condition above always exists.

以下是你要的代码： ```c++ #include <iostream> #include <algorithm> using namespace std; const int MAXN = 105; int a[MAXN], b[MAXN]; int main() { int t; cin >> t; while (t--) { int n; cin >> n; for (int i = 0; i < n; i++) { cin >> a[i]; } sort(a, a + n); int l = 0, r = n - 1; for (int i = 0; i < n; i++) { if (i % 2 == 0) { b[i] = a[l]; l++; } else { b[i] = a[r]; r--; } } for (int i = 0; i < n; i++) { cout << b[i] << " "; } cout << endl; } return 0; } ``` 思路：首先将原排列 a 排序，然后将排序后的元素分成两部分，分别从前往后和从后往前取，这样可以保证 b 满足题目要求。

<think>嗯，我现在得解决这个问题。题目是说，给一个排列p，找出满足条件[a,b,c,d]四元组的数量。条件是a < b < c < d，同时满足pa < pc 且 pb > pd。这个问题看起来有点挑战性，我得仔细想想怎么高效地计算符合条件的四元组数目。 首先，我得理解问题。排列中的每个元素都是唯一的，所以不会有重复的值。四元组的四个索引必须严格递增，即a < b < c < d。然后，要满足pa < pc和pb > pd。我需要找到所有这样的四元组的数量。 直接暴力的方法是枚举所有可能的a、b、c、d，然后检查条件。不过这样的话，时间复杂度会是O(n^4)，当n到5000的时候，这显然是不行的。因为n=5000的话，n^4是大约6e17次运算，完全无法处理。所以必须想更高效的方法。 那有没有办法通过预处理或者分解问题来减少复杂度呢？比如，固定某些中间的两个点，然后计算前后可能的组合数？ 例如，考虑中间的两个位置是b和c，或者b和d？或者别的组合？ 题目中的两个条件pa < pc和pb > pd，可能需要将这两个条件分开考虑，或者找到它们之间的联系。 另一个思路是，对于每个可能的b和c的组合（其中b < c），然后计算满足a < b且pa < pc的a的数量，以及满足d > c且pb > pd的d的数量，然后将这两个数相乘，得到对于这个b和c的所有可能的四元组数目。然后将所有b和c的组合情况累加起来。 这可能是一个可行的方法。因为如果固定b和c，那么a必须属于1到b-1，d必须属于c+1到n。然后，对于每个这样的a，检查pa是否小于pc；对于每个d，检查pb是否大于pd。然后这两部分的数目相乘，就是对于当前b和c的四元组数目。 这样的话，总的时间复杂度是O(n^2)乘以每个b和c的处理时间。假设预处理可以在O(1)时间内得到每个b和c对应的a的数量和d的数量，那么总的时间复杂度是O(n^2)，这应该可以处理n=5000的情况，因为5000^2是25,000,000，应该是可以接受的。 那现在的问题转化为，如何高效地预处理每个可能的b和c对应的满足条件的a的数量和d的数量。 对于每个c来说，我们可以预处理每个可能的b（b < c），然后计算有多少a < b使得pa < pc。这部分可以预先处理吗？ 或者，对于每个c，我们可以提前记录每个位置左边的各个位置的pa值。比如，对于每个c，可以预处理一个数组left[c][b]，表示在位置b的左边（即a < b）有多少个a满足pa < pc。这里，b的取值范围是1到c-1，而c的取值范围是1到n。 同样的，对于每个b，我们可以预处理一个数组right[b][c]，表示在位置c的右边（即d > c）有多少个d满足pd < pb。因为pb是固定的，对于每个b来说，我们需要统计在d > c的情况下pd < pb的数量。或者，可能这里需要更仔细的处理。 或者，我们可以这样想： 对于每个可能的b和c（其中b < c），我们需要计算： - a的数目：在a < b的位置中，pa < pc的数量。这可以看作对于每个c，预先计算对于每个可能的b（b < c），有多少个a在[1, b-1]范围内满足pa < pc。 - d的数目：在d > c的位置中，pd < pb的数量。因为pb是已知的，所以对于每个b，我们可以预先统计在某个c的右边（d >c）有多少个d满足pd < pb。 或者，可能需要另一个预处理方式。例如，对于每个b，预处理一个数组，记录在位置d > c时，pd的值是否小于pb。但这样可能无法直接使用，因为c的位置会影响d的选择范围。 或者，可以换个角度。当固定了b和c之后，d必须满足d > c，并且pd < pb。所以，对于每个b，我们可以预处理一个数组，统计从某个位置开始（比如从c+1到n）有多少个d满足pd < pb。这样，当处理到某个c时，对于b来说，d的范围是c+1到n，所以需要知道在这个区间内有多少个pd < pb。 这个预处理可能需要二维数组，比如right[b][k]，表示从位置k到n中，有多少个d满足pd < pb。这样，对于给定的b和c，d的数量就是right[b][c+1]。这样，预处理每个b的前缀和或者后缀和。 同样的，对于a的条件，固定c后，需要找出在a < b的位置中，有多少个pa < pc。这可以预处理为left[c][b]，表示在a < b的范围内，pa < pc的数目。这时候，对于每个c，可以预处理每个b的left[c][b]。 现在的问题是，如何高效地预处理这两个数组。 对于left[c][b]：对于每个c，遍历所有可能的b（b的范围是1到c-1），然后统计在a < b时，pa < pc的数量。这可以在预处理时，对于每个c，维护一个前缀数组。例如，对于每个c，我们可以从左到右遍历b，并维护一个计数器，记录有多少个a在b之前（即a < b）满足pa < pc。这可能可以用一个前缀和数组来实现。比如，pre_left[c]是一个数组，pre_left[c][b]表示从a=1到a=b-1，满足pa < pc的数目。这样，当处理到c的时候，可以遍历每个b从1到c-1，并计算pre_left[c][b]的值。这可能需要O(n^2)的时间，因为对于每个c，遍历b到c-1，每个c的复杂度是O(n)，总共有n个c，所以总的时间复杂度是O(n^2)。这可能可行，因为n=5000的话，5000^2是25e6，可以接受。 同样，对于right[b][c]：对于每个b，预处理每个c >= b+1的位置，统计在d > c时，有多少个d满足pd < pb。或者，可能更合适的预处理方式是，对于每个b，预处理一个后缀数组，表示从某个位置到n之间有多少个pd < pb。例如，right_suffix[b][k]表示从位置k到n中，pd < pb的数量。这样，当给定c时，d的范围是c+1到n，所以right_suffix[b][c+1]就是对应的数目。这个预处理同样可以通过对每个b，从后往前遍历，统计满足条件的数目，并存储到right_suffix数组中。预处理的时间复杂度也是O(n^2)。 一旦这两个预处理数组pre_left和right_suffix准备好，那么对于每个可能的b和c（其中b < c），我们可以得到对应的a的数量是pre_left[c][b]，而d的数量是right_suffix[b][c+1]。然后将这两个数相乘，得到所有以b和c为中间两个点的四元组数目。然后将所有这些数目相加，总和就是最终的答案。 那么，整体的步骤应该是： 1. 预处理pre_left数组：对于每个c，计算pre_left[c][b]，其中b的取值范围是1到c-1。pre_left[c][b]表示在a < b时，pa < pc的数目。 如何计算pre_left[c][b]？ 可以对于每个c，初始化一个数组cnt，初始化为0。然后遍历b从1到n。当处理b的时候，如果b < c，那么判断p[b]是否小于p[c]。如果是，就将cnt增加1。pre_left[c][b]的值就是当前的cnt。但这样可能有问题，因为对于不同的c，每个b的处理方式不同。或者，对于每个c，我们遍历b从1到c-1，并在每个步骤中统计前面有多少个a满足pa < pc。 例如，对于每个c，pre_left[c][b] 的值为从a=1到a=b-1中满足pa < pc的数目。那么，我们可以按如下方式处理： 对于每个c，初始化一个计数器count=0。然后，遍历b从1到c-1： pre_left[c][b] = count的值，此时count是a < b的数目。然后，当处理到b时，如果当前的p[b] < p[c]，那么当后续的b' >b时，这个a=b会被包含进去吗？或者，这个计数是累计的？ 可能更正确的方式是，对于每个c，从左到右遍历b从1到n。对于每个b，如果b < c，则pre_left[c][b]等于在a < b的位置中满足pa < pc的数量。这时候，可以用一个循环，每个c的处理如下： pre_left[c]是一个数组，大小为n+1。初始化为0。 count = 0; for (int b=1; b <= c-1; b++) { if (p[b] < p[c]) { count++; } pre_left[c][b] = count; } 这样，pre_left[c][b]的值就是当a的取值范围是1到b时，满足pa < pc的数目。例如，当b=3时，pre_left[c][3]就是a=1、2、3中的满足条件的数目？或者这里可能有一个错误。比如，对于b来说，a的取值范围是1到b-1。比如，当b=1的时候，没有a的可能。所以，正确的处理应该是在每个b的循环中，pre_left[c][b] 的值是当b的位置时，a可以取到1到b-1中的数目。 所以，正确的处理应该是： 对于每个c： 初始化count=0; pre_left[c][0] =0; for (int b=1; b < c; b++) { // 处理a的取值范围是1到b-1。所以，当b=1时，a只能是0个，所以pre_left[c][1] =0. // 在b循环中，每次处理的是当b增加时，当前p[b]是否小于pc，从而影响后面的pre_left的值。 // 例如，当b=2的时候，a的取值范围是1到1。此时，pre_left[c][2]等于count的值，即前面所有b' <2的满足条件的情况？ // 所以，正确的处理是，当处理到b时，pre_left[c][b]的值是count的值，然后判断p[b]是否小于pc，如果是，则count加一。 // 这样，对于下一个b+1，pre_left[c][b+1]的初始值是count的当前值，也就是在b之前的满足条件的数目。 // 所以，pre_left[c][b] = count的值，即当a的取值范围是1到b-1时，满足条件的数目。 pre_left[c][b] = count; if (p[b] < p[c]) { count++; } } 这样，当b遍历到c-1时，pre_left[c][b]的值是a从1到b-1的数目。例如，当c=4，b=3时，pre_left[4][3]是a=1和2的数目。然后，如果p[3] < p[4]，则count会增加。 这样，对于每个c来说，pre_left[c][b] 的值是正确的。 例如，假设c=5，p[5]=10。当处理b=3时，pre_left[5][3]的值是a=1、2中的满足条件的数目。然后判断p[3]是否小于10，如果是，count加一。这个count的值将用于下一个b的pre_left的值。 这样处理的话，pre_left数组的预处理复杂度是O(n^2)。 接下来是预处理right_suffix数组。right_suffix[b][k]表示从位置k到n中，满足pd < pb的数目。例如，当给定b和c时，d必须大于c，所以k=c+1。right_suffix[b][k]的值就是满足条件的d的数量。 如何预处理这个数组？ 可以对于每个b，从n到1的方向处理，维护一个数组，记录每个位置k到n的满足条件的数目。 具体来说，对于每个b，我们初始化一个数组right_suffix[b]，长度为n+2（因为k的范围是1到n+1）。 初始化right_suffix[b][n+1] =0; 然后，从k=n downto 1: right_suffix[b][k] = right_suffix[b][k+1] + (p[k] < p[b] ? 1 : 0); 这样，对于每个位置k，right_suffix[b][k]等于k到n中满足pd < pb的数量。 这样预处理的时间复杂度也是O(n^2)。 一旦这两个预处理完成，那么对于每个四元组中的可能的b和c（b < c），其贡献的数目是pre_left[c][b] * right_suffix[b][c+1]。然后将所有可能的b和c的组合的贡献相加，得到总和。 现在的问题是如何枚举b和c的可能组合。因为a必须小于b，c必须大于b，而d必须大于c。因此，b必须小于c。所以，b和c的可能取值范围是1 <= b < c <=n。然后，对于每个这样的b和c，计算贡献。 但是，题目中的四元组要求是a < b < c < d。所以，在四元组中，a <b，b <c， c <d。所以，b可以是任何介于a和c之间的位置，但这里的处理方式已经将b和c固定，所以只要枚举所有满足b < c的情况，然后确保在计算a的时候，a <b，并且d >c即可。 因此，正确的枚举方式是遍历所有可能的b和c，其中b < c。然后，对于每个这样的b和c，计算pre_left[c][b]（即a的数目）乘以 right_suffix[b][c+1]（即d的数目），并将结果累加。 那这样的时间复杂度是O(n^2)，这应该可以在时间限制内完成。 现在需要考虑边界情况。例如，当c=4时，c+1=5，如果n=4的话，那么d必须大于4，所以没有可能的d。此时right_suffix[b][5]的值是0。这样，乘的时候，贡献就是0，所以不影响总和。 同样的，当b=1时，a的数目是pre_left[c][1]的值。根据之前的预处理，pre_left[c][1]等于0，因为a必须小于1，即a只能是0，所以数目为0。因此，这种情况会被自动处理。 现在，如何实现这个预处理？ 在代码中，可以这样实现： 预处理pre_left： pre_left是一个二维数组，大小为n+1（c的范围是1到n）乘n+1（b的范围是1到n）。 对于每个c，从1到n： count =0; pre_left[c][0] =0; for (b=1; b < c; b++){ pre_left[c][b] = count; if (p[b] < p[c]) { count++; } } 或者，在代码中，可以使用动态数组，比如用vector<vector<int>> pre_left(n+1, vector<int>(n+1, 0))。但n是5000的话，这样的二维数组需要5000*5000=25e6的存储空间，这在C++中是可行的。 预处理right_suffix： right_suffix也是一个二维数组，大小为n+1（b的范围是1到n）乘n+2（k的范围是1到n+1）。 对于每个b，从1到n： right_suffix[b][n+1] =0; for (int k=n; k >=1; k--){ right_suffix[b][k] = right_suffix[b][k+1] + (p[k] < p[b] ? 1 : 0); } 然后，枚举所有的b和c，其中b <c: long long ans =0; for (int c=1; c <=n; c++){ for (int b=1; b <c; b++){ int a_count = pre_left[c][b]; int d_count = right_suffix[b][c+1]; ans += a_count * d_count; } } 这样就得到了最终的结果。 现在，测试一下这个方法是否正确。例如，考虑一个小例子： 假设n=4，排列是[1,3,2,4]。 那么，满足条件的四元组有哪些？ 可能的四元组是[a,b,c,d]，其中a <b <c <d。需要满足pa < pc且 pb > pd。 例如，假设a=1，b=2，c=3，d=4： pa=1，pc=2 → 1<2成立。pb=3，pd=4 →3>4不成立。所以这个组合不满足。 另一个可能的四元组是a=1，b=3，c=4，d=不存在，因为d必须>4，但n=4，所以不可能。 或者，可能还有其他组合。例如，假设排列是[2,4,1,3]。此时，可能有一些符合条件的四元组。 例如，考虑n=5，排列是5,3,1,2,4。这时候，可能有符合条件的四元组吗？ 或者，先举一个更简单的例子。比如，当n=4，排列是[2,4,1,3]。要找到所有可能的四元组。 四元组的条件是a <b <c <d，所以可能的四元组只能是 [1,2,3,4]。这里，a=1，b=2，c=3，d=4。检查条件： pa=2 < pc=1？ 不成立。所以不满足条件。所以这个四元组无效。 另一个可能的排列是[1,4,2,3]。此时，四元组只能是[1,2,3,4]。检查条件： pa=1 < pc=2 →成立。 pb=4 > pd=3 →成立。所以这个四元组是有效的。因此，答案是1。 现在用代码来验证： 预处理pre_left： 对于c=3（pc=2）： pre_left[3][b] for b from 1 to 2. 当处理c=3: b=1: pre_left[3][1] =0（因为count初始为0）。然后判断p[1]=1 <2，所以count增加到1。 b=2: pre_left[3][2] =count的当前值1。此时，判断p[2]=4 <2？不成立。count保持1. 所以pre_left[3][2] =1。这表示当c=3，b=2时，a的数目是1。因为a必须小于b=2，所以a只能是1。此时，pa=1 < pc=2，所以正确。 right_suffix[b=2][c+1=4]：即当b=2，k=4。因为p[4]=3 < p[2]=4 →是。所以right_suffix[2][4] =1（因为k=4到4，只有一个元素3，符合条件）。 所以，当c=3，b=2时，贡献为1*1=1。同时，其他可能的b和c的组合是否还有？ 例如，考虑c=4，b=2： pre_left[4][b=2] =在c=4时，pa < p[4]=3的条件。p[4]是3。所以，当b=2时，a必须是<2的位置，即a=1。判断p[1]=1 <3，是的。所以pre_left[4][2] =1。然后，right_suffix[b=2][c+1=5]即k=5的位置，此时right_suffix[2][5] =0。所以贡献是1*0=0。 可能还有其他组合，比如当c=3，b=2的情况下贡献了1。所以总和是1，与实际例子中的正确结果一致。 这说明代码是正确的。 现在，需要考虑代码的编写。在C++中，需要注意数组的索引是否正确。例如，排列p的索引是否从1开始？题目中给出的输入是p1,p2,…,pn，所以代码中的数组应该从1开始存储。 此外，要注意数据范围，答案可能很大，需要用long long类型来存储总和。 现在，编写代码的大致步骤： 读取t个测试用例。对于每个测试用例： 读取n和p数组（假设p的索引是1-based）。 预处理pre_left数组： pre_left是一个二维数组，pre_left[c][b] 表示对于c来说，当b是某个值时，a的数目。 预处理right_suffix数组： right_suffix是一个二维数组，right_suffix[b][k]表示对于b来说，从k到n满足pd < pb的数目。 计算总和ans： 遍历每个c和每个b <c，ans += pre_left[c][b] * right_suffix[b][c+1]. 然后输出ans. 这样应该可以得到正确的结果。 现在，测试代码的时间复杂度。例如，对于每个测试用例，预处理pre_left和right_suffix各需要O(n^2)时间，然后枚举所有b和c的组合需要O(n^2)时间。所以总的时间复杂度是O(n^2)。对于n=5000，每个测试用例的处理时间是大约3*5000^2=75e6操作，这在C++中应该可以处理，因为每秒大约可以处理1e8次操作。 但是，当t=1000，且每个测试用例的n=5，那么总的时间是1000*(3*25) =75000，这也没问题。但题目中给出的约束是，所有测试用例的n的总和不超过5000。例如，如果有1000个测试用例，每个n=5，总和是5000。这时候，总的时间是3*(5000)^2=75e6，这没问题。所以这样的算法是可行的。 现在，编写代码的具体实现： 在C++中，使用vector来存储pre_left和right_suffix可能效率不高，因为5000x5000的数组会占用较多内存，但可以使用二维数组或者动态数组。或者，可以用二维数组，因为n最多是5000，所以每个测试用例可以动态分配。 例如，每个测试用例的处理步骤： int n; cin >>n; vector<int> p(n+1); // p[1..n] for(int i=1; i<=n; i++) cin >>p[i]; 然后，预处理pre_left： vector<vector<int>> pre_left(n+2, vector<int>(n+2, 0)); for(int c=1; c <=n; c++){ int count=0; for(int b=1; b <c; b++){ pre_left[c][b] = count; if(p[b] < p[c]){ count++; } } } 预处理right_suffix： vector<vector<int>> right_suffix(n+2, vector<int>(n+2, 0)); for(int b=1; b <=n; b++){ right_suffix[b][n+1] =0; for(int k=n; k >=1; k--){ right_suffix[b][k] = right_suffix[b][k+1] + (p[k] < p[b] ? 1 : 0); } } 然后计算ans： long long ans =0; for(int c=1; c <=n; c++){ for(int b=1; b <c; b++){ int a_count = pre_left[c][b]; int d_count = right_suffix[b][c+1]; ans += (long long)a_count * d_count; } } cout <<ans <<endl; 这应该可以解决问题。 现在，测试这个代码是否正确。例如，前面的例子： 测试用例： 1 4 1 4 2 3 根据之前的分析，正确的答案是1。现在，代码运行时的处理： pre_left[c=3][b=2]的情况： p[3]=2. 当处理c=3: b从1到2. b=1: pre_left[3][1] =0. 检查p[1]=1 <2 →count变为1. b=2: pre_left[3][2] =count的值1。此时，p[2]=4>2，不增加count. 所以pre_left[3][2] =1. right_suffix[b=2][c+1=3+1=4]。其中，b=2的p[b]=4. right_suffix[2][4]等于从位置4到n=4中，p[4]=3 <4的数量，即1. 所以贡献是1*1=1. 其他可能的b和c的组合是否有贡献？ 比如，c=4，b=3： pre_left[4][3] 的值。此时c=4，p[4]=3. 在b=3时，遍历到b=3，但c=4，所以b <c成立。 pre_left[4][3]等于之前的count的值。在处理c=4时，b的范围是1到3. b=1：判断p[1]=1 <3 →count变为1. b=2：判断p[2]=4 <3 →不，count保持1. pre_left[4][2] =1. b=3: pre_left[4][3] =count的值是1（因为之前的处理是，在b=3之前的count是1？或者需要仔细看循环的处理。 预处理c=4时，循环b从1到3. 初始count=0. 当b=1： pre_left[4][1] =0. p[1]=1 <3 →count变为1. b=2： pre_left[4][2] =1. p[2]=4 <3？不 →count保持1. b=3: pre_left[4][3] =1. p[3]=2 <3 →count变为2. 所以pre_left[4][3] =1. 此时，right_suffix[b=3][c+1=4+1=5] →k=5不存在，所以right_suffix[3][5]=0. 所以贡献是1*0=0. 所以，这个四元组的贡献为0. 其他可能的组合： 比如，c=4，b=2： pre_left[4][2] =1. p[4]=3的条件是，在b=2的情况下，a可以取1到1的位置。此时，pa=1 <3，所以数目是1。pre_left[4][2] =1. right_suffix[b=2][c+1=5] →k=5，返回0。所以贡献是1*0=0. 所以，只有c=3，b=2的情况下贡献1，总和是1，正确。 这说明代码是正确的。 因此，最终的代码应该能够正确处理问题。</think>要解决这个问题，我们需要找到满足特定条件的四元组 [a, b, c, d] 的数量，其中 a < b < c < d，并且满足 pa < pc 和 pb > pd。直接枚举所有可能的四元组会导致无法接受的时间复杂度，因此我们需要优化算法。 ### 方法思路 1. **预处理左侧信息**：对于每个位置 c，预处理每个位置 b < c 的左侧满足 pa < pc 的数量。 2. **预处理右侧信息**：对于每个位置 b，预处理每个位置 c 的右侧满足 pd < pb 的数量。 3. **组合结果**：对于每个可能的 (b, c) 组合，计算满足条件的左侧和右侧数量的乘积，并累加所有结果。 ### 解决代码 ```cpp #include <iostream> #include <vector> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int t; cin >> t; while (t--) { int n; cin >> n; vector<int> p(n + 1); for (int i = 1; i <= n; ++i) { cin >> p[i]; } // 预处理pre_left[c][b]，表示对于c来说，a在1..b-1中有多少满足pa < pc vector<vector<int>> pre_left(n + 2, vector<int>(n + 2, 0)); for (int c = 1; c <= n; ++c) { int count = 0; for (int b = 1; b < c; ++b) { pre_left[c][b] = count; if (p[b] < p[c]) { ++count; } } } // 预处理right_suffix[b][k]，表示对于b来说，从k到n中有多少满足pd < pb vector<vector<int>> right_suffix(n + 2, vector<int>(n + 2, 0)); for (int b = 1; b <= n; ++b) { right_suffix[b][n + 1] = 0; for (int k = n; k >= 1; --k) { right_suffix[b][k] = right_suffix[b][k + 1] + (p[k] < p[b] ? 1 : 0); } } long long ans = 0; for (int c = 1; c <= n; ++c) { for (int b = 1; b < c; ++b) { int a_count = pre_left[c][b]; int d_count = right_suffix[b][c + 1]; ans += static_cast<long long>(a_count) * d_count; } } cout << ans << '\n'; } return 0; } ``` ### 代码解释 1. **输入处理**：读取输入数据，包括测试用例数量和每个排列。 2. **预处理左侧信息**：对于每个位置 c，计算每个位置 b < c 的左侧满足条件的数量。 3. **预处理右侧信息**：对于每个位置 b，计算从每个位置 k 到末尾满足条件的数量。 4. **组合结果**：遍历所有可能的 (b, c) 组合