ACM-ICPC-OJ训练营

问题 2908 --D.弹球（HARD）(暴力+贪心+双指针)

2908: D.弹球（HARD）(暴力+贪心+双指针)

时间限制: 1 Sec 内存限制: 256 MB
提交: 0 解决: 2
[提交][状态][讨论版][命题人:]

题目描述

与easy版本的区别在于数据的范围

给你一个长度为n的排列组合p.
一个排列组合是由1到n的n个不同的整数按任何顺序组成的。例如，{2,3,1,5,4}是一个排列组合，而{1,2,2}不是（因为2出现了两次），{1,3,4}也不是一个排列组合（因为n=3，但数组中包含4).
对于排列组合p，你需要应用下面的操作正好一次：
首先你选择一个段[l,r]。(1≤l≤r≤n，一个段是一个连续的数字序列{p_l,p_l+1,...,p_r-1,p_r})并将其倒置。
然后你交换前缀和后缀：[r+1,n]和[1,l-1]（注意，这些段可能是空的）。
例如，给定n=5,p={2,3,1,5,4}，如果你选择段[l=2,r=3]，在颠倒段p={2,1,3,5,4}后，就把段[4,5]和[1,1]交换。因此，p={5，4，1，3，2}。.可以证明这是给定的排列组合的最大可能结果。
你需要输出通过精确应用一次所述操作可以得到的字典序上的最大排列组合。

输入描述

输入的第一行包含一个整数t（1≤t≤1000)--测试用例的数量。
然后是测试用例的描述。
每个测试用例的第一行包含一个整数n（1≤n≤200000)-- p的大小。
每个测试用例的第二行包含n个整数：p1,p2,...,pn（1≤pi≤n）--包函p本身。
可以保证所有测试用例的n之和不超过200000。

输出描述

对于每个测试案例，在一行中输出长度为n的最大排列组合，题目保证一定有解

样例输入

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

样例输出

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

提示

第一个例子在问题陈述中已经说明。

在第二个例子中，应选择[l=9,r=9]这一段。

在第三个例子中，应选择[l=1,r=1]段。

在第四个例子中，应选择[l=1,r=2]段。

在第五个例子中，应选择[l=5,r=6]段。

在第六个例子中，应该选择[l=4,r=4]段。

在第七个例子中，应该选择段[l=5,r=5]。

来源

22计1张德鸿CF874(div3).D

[提交][状态]