Cat, Fox and Double Maximum

题面翻译

给你一个偶数 $n$ 和一个长度为 $n$ 的排列 $p$。让你构造另一个长度为 $q$ 的排列，把 $p$ 和 $q$ 加起来得到一个新的长度为 $n$ 的序列 $a$，即 $a_i=p_i+q_i$。

要求通过 $q$ 计算出的 $a$ 满足有最多的 局部最大值。

局部最大值是指对于一个位置 $i(1<i<n)$，$a_i>a_{i-1}$ 且 $a_i>a_{i+1}$。

输出任意一个最优的 $q$。

题目描述

Fox loves permutations! She came up with the following problem and asked Cat to solve it:

You are given an even positive integer $ n $ and a permutation $ ^\dagger $ $ p $ of length $ n $ .

The score of another permutation $ q $ of length $ n $ is the number of local maximums in the array $ a $ of length $ n $ , where $ a_i = p_i + q_i $ for all $ i $ ( $ 1 \le i \le n $ ). In other words, the score of $ q $ is the number of $ i $ such that $ 1 < i < n $ (note the strict inequalities), $ a_{i-1} < a_i $ , and $ a_i > a_{i+1} $ (once again, note the strict inequalities).

Find the permutation $ q $ that achieves the maximum score for given $ n $ and $ p $ . If there exist multiple such permutations, you can pick any of them.

$ ^\dagger $ 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).

输入格式

The first line of input contains an integer $ t $ ( $ 1 \leq t \leq 10^4 $ ) — the number of test cases in the input you will have to solve.

The first line of each test case contains one even integer $ n $ ( $ 4 \leq n \leq 10^5 $ , $ n $ is even) — the length of the permutation $ p $ .

The second line of each test case contains the $ n $ integers $ p_1, p_2, \ldots, p_n $ ( $ 1 \leq p_i \leq n $ ). It is guaranteed that $ p $ is a permutation of length $ n $ .

It is guaranteed that the sum of $ n $ across all test cases doesn’t exceed $ 10^5 $ .

输出格式

For each test case, output one line containing any permutation of length $ n $ (the array $ q $ ), such that $ q $ maximizes the score under the given constraints.

样例 #1

样例输入 #1

4
4
1 2 3 4
4
4 3 1 2
6
6 5 1 4 2 3
8
1 2 4 5 7 6 8 3

样例输出 #1

2 4 1 3
3 1 4 2
2 5 1 4 3 6
5 4 8 2 7 1 6 3

提示

In the first example, $ a = [3, 6, 4, 7] $ . The array has just one local maximum (on the second position), so the score of the chosen permutation $ q $ is $ 1 $ . It can be proven that this score is optimal under the constraints.

In the last example, the resulting array $ a = [6, 6, 12, 7, 14, 7, 14, 6] $ has $ 3 $ local maximums — on the third, fifth and seventh positions.

解

显然我们可以构造排列 q使得所有qi+pi=n+1
这样可以先让所有数相等，方便我们构造。
我们可以令 q 所有偶数位置加一，奇数位置不变，显然这是我们最多只能有这么多局部最大值。但是这不符合 q 所有元素不重复的要求，考虑去重。
由于重复元素是由于偶数位置的数增大导致的，那么一定有原本较小的数没有使用。
因此我们可以用这些较小数来替换奇数位置重复的数，显然这并不会影响局部最大值的数量。
直接将这些没有使用的数排序，把奇数位置的数也排序，按排名依次替换即可。
这里有一个问题，如果偶数位置上存在n导致其无法加一，怎么办？依旧按上面的构造方式，奇偶互换即可。

const int N = 200010;
int a[N];
int b[N];
int c[N];
int cmp(int x, int y)
{
    return x > y;
}
void solve()
{
    int n;
    cin >> n;
    int xb = 0;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        if (a[i] == 1) xb = i;
    }
    int yb = 0;
    if (xb % 2 == 0) xb = 1, yb = 2;
    else xb = 2, yb = 1;

    map<int, int> p;
    for (int i = xb; i <= n; i += 2)
    {
        b[i] = n - a[i] + 1 + 1;
        p[b[i]] = 1;
    }
    int h = 0;
    for (int i = yb; i <= n; i += 2) c[++h] = a[i];
    sort(c + 1, c + 1 + h,cmp);
    map<int, int> q;
    int fw = 1;
    for (int i = 1; i <= h; i++) {
        while (p[fw] == 1) fw++;
        q[c[i]] = fw;
        fw++;
    }
    for (int i = yb; i <= n; i += 2) b[i] = q[a[i]];
    for (int i = 1; i <= n; i++) cout << b[i] << " ";
    cout << '\n';