ZUFEOJ Home ProblemSet Source/Category Contest Status Ranklist F.A.Qs ContestProblemSetList
Login Register

问题 H: 学高考第19题导致的

内存限制：1024 MB 时间限制：4 S
题面：传统 评测方式：文本比较 上传者：
提交：4 通过：3
返回比赛提交提交记录

题目描述

给定一个 n 项的数列 a，对于 1 ≤ i, j ≤ n，我们称 i ≺a j 当且仅当 i <j 并且 ai> max ak。
2≤k≤j
你可以任意选择一个 1 ~ n 的排列 p，并令 bi = ap (i)，相似地定义二元关系 ≺b，但要求：对于任意 1 ≤ i, j ≤ n，p (i) ≺a p (j) 当且仅当 i ≺b j。
求能得到的数列 b 中字典序最大的一个。

输入格式

本题输入有多个测试数据。输入的第一行有一个正整数 T（1 ≤ T ≤ 10⁴）。
每组测试数据分为两行。

  • 第一行为一个正整数 n（1 ≤ n ≤ 3 × 10⁵），表示数列 a 的长度。
  • 第二行有 n 个正整数 a1, a2, …, an（1 ≤ ai ≤ 10⁹），表示初始时的数列 a。
    对于全体数据，保证所有测试点的 n 之和不超过 10⁶。

输出格式

对于每组数据，输出一行 n 个正整数，表示数列 b 字典序的最大可能值。

输入样例 复制 

1
11
5 9 8 4 6 8 9 8 8 4 7

输出样例 复制 

5 9 8 8 4 7 9 8 8 4 6

数据范围与提示

令 p (1), …, p (11) 依次为 1, 7, 8, 9, 10, 11, 2, 6, 3, 4, 5 即可。
下面以其中几对 (i, j) 为例，验证 p 是符合条件的：

  • 若 i = 7, j = 11，则 p (i) = 2, p (j) = 5，ap (i) = 9 > max ak = 8，因此 p (i) ≺a p (j)。对应地，bi = 9 > max bk = 8，因此 i ≺b j。
    2≤k≤5 7≤k≤11
  • 若 i = 7, j = 2，则 p (i) = 2, p (j) = 7，ap (i) = 9 > max ak = 9，因此 p (i)≮a p (j)。对应地，i > j 所以 i≮b j。
    2≤k≤7
    可以证明，无法产生字典序更大的排列。