Codeforces Round #704 (Div. 2)-B. Card Deck

傳送門
Time Limit: 1 second
Memory Limit: 512 megabytes

Problem Description

You have a deck of n n n cards, and you’d like to reorder it to a new one.

Each card has a value between 1 1 1 and n n n equal to p i p_i pi?. All p i p_i pi? are pairwise distinct. Cards in a deck are numbered from bottom to top, i. e. p 1 p_1 p1? stands for the bottom card, p n p_n pn? is the top card.

In each step you pick some integer k > 0 k > 0 k>0, take the top k k k cards from the original deck and place them, in the order they are now, on top of the new deck. You perform this operation until the original deck is empty. (Refer to the notes section for the better understanding.)

Let’s define an order of a deck as ∑ i = 1 n n n ? i ? p i \sum\limits_{i = 1}^{n}{n^{n - i} \cdot p_i} i=1∑n?nn?i?pi?.

Given the original deck, output the deck with maximum possible order you can make using the operation above.

Input

The first line contains a single integer t t t ( 1 ≤ t ≤ 1000 1 \le t \le 1000 1≤t≤1000) — the number of test cases.

The first line of each test case contains the single integer n n n ( 1 ≤ n ≤ 1 0 5 1 \le n \le 10^5 1≤n≤105) — the size of deck you have.

The second line contains n n n integers p 1 , p 2 , … , p n p_1, p_2,\dots, p_n p1?,p2?,…,pn? ( 1 ≤ p i ≤ n 1 \le p_i \le n 1≤pi?≤n; p i ≠ p j p_i \neq p_j pi??=pj? if i ≠ j i \neq j i?=j) — values of card in the deck from bottom to top.

It’s guaranteed that the sum of n n n over all test cases doesn’t exceed 1 0 5 10^5 105.

Output

For each test case print the deck with maximum possible order. Print values of cards in the deck from bottom to top.

If there are multiple answers, print any of them.

Sample Input

4
4
1 2 3 4
5
1 5 2 4 3
6
4 2 5 3 6 1
1
1

Sample Onput

4 3 2 1
5 2 4 3 1
6 1 5 3 4 2
1

Note

In the first test case, one of the optimal strategies is the next one:

In the second test case, one of the optimal strategies is:

In the third test case, one of the optimal strategies is:

題目大意

有一摞牌（A），要把它移成另一摞（B），
每次可以拿走最上面的幾張放到另一摞（B），
直到最終全部由（A）移到（B），
越往下權值越高，問總值最大的話（B）長什么樣，

題目分析

首先不難看出牌大的盡量放到最下面，

優于

所以每次就把最大的放到最下面，
同時位于最大的上面的也必須連帶地移到（B）去，
重復操作直到（A）中牌全部移動到（B），

如：

4 2 5 3 6 1中最大的是6，就把6 1移動到（B）

4 2 5 3和6 1，然后左邊沒有移動的（A）中最大的是5，就把5 3移動到（B）

4 2和6 1 5 3，然后左邊沒有移動的（A）中最大的是4，就把4 2移動到（B）

（A）空，得到（B）6 1 5 3 4 2即為答案，

解題思路

每次從頭遍歷到尾找最大 O O O ( ( ( n 2 n^{2} n2 ) ) )肯定要超時，
不難發現其實每次找到當前最大，放到隊尾即可，

初始最大值為第一個數 4 4 4
4 2 5 3 6 1從第一個數開始往后找，直到找到5>4，然后就把4 2放到輸出答案的最后，

5 3 6 1和4 2，再往后找，6>5，把5 3放到輸出答案的最后的前一個，

6 1和5 3 4 2，最后把6 1放到輸出答案的前一個，

6 1 5 3 4 2即為最終答案，

這個程序可以用堆疊來實作，
要放4 2，就先2入堆疊后4入堆疊，
然后放5 3，就先3入堆疊后5入堆疊，
最后放6 1，就先1入堆疊后6入堆疊，
然后堆疊為

出堆疊順序為

即為所求，

AC代碼

#include <bits/stdc++.h>
using namespace std;
#define mem(a) memset(a, 0, sizeof(a))
#define dbg(x) cout << #x << " = " << x << endl
#define fi(i, l, r) for (int i = l; i < r; i++)
#define cd(a) scanf("%d", &a)
typedef long long ll;
int a[100010];
void push(stack<int> &s, int l, int r) //從l到r入堆疊
{
    for (int i = r; i >= l; i--) //小的先入堆疊（從右往左）
        s.push(a[i]);
}
/*列印堆疊*/
void prt(stack<int> &s)
{
    while (s.size()) //非空時出堆疊
    {
        printf("%d ", s.top());
        s.pop();
    }
    puts(""); //換行
}
int main()
{
    int N;
    cin >> N;
    while (N--) //N組資料
    {
        stack<int> s;
        int n;
        cd(n); //scanf("%d",&n);
        for (int i = 0; i < n; i++)
            cd(a[i]); //scanf("%d",&a[i]);
        a[n] = n + 1; //最后設定一個最大的數，保證前面所有都比它小
        int M = a[0], last = 0;
        for (int i = 0; i <= n; i++)
        {
            if (a[i] > M) //找到一個更大的數
            {
                push(s, last, i - 1); //入堆疊并更新
                last = i; 
                M = a[i];
            }
        }
        prt(s); //列印
    }
    return 0;
}