题目描述

Farmer John 有 NN（1≤N≤2⋅1051≤N≤2⋅105）头奶牛排成一条队伍 aa。队伍 aa 中从前到后第 ii 头奶牛编号为一个整数 aiai​（1≤ai≤N1≤ai​≤N）。可能存在多头奶牛编号为同一整数。

FJ 将以以下方式构造另一条队伍 bb：

• 初始时，bb 为空。
• 当 aa 非空时，移除 aa 最前面的奶牛，并选择是否将该奶牛添加到 bb 的最后。

FJ 想要构造队伍 bb，使得 bb 中从前到后的编号序列是字典序最大的（见脚注）。

在 FJ 构造队伍 bb 之前，他可以执行以下操作至多一次：

• 选择队伍 aa 中的一头奶牛，并将其移动至当前位置之前的任意位置。

假设 FJ 以最优方式执行至多一次上述操作，输出他可以达到的字典序最大的 bb 的编号序列。

每个测试点将包含 TT（1≤T≤1001≤T≤100）个独立的测试用例。

输入格式

输入的第一行包含 TT。

每一个测试用例的第一行包含 NN。

每一个测试用例的第二行包含 NN 个空格分隔的整数 a1,a2,…,aNa1​,a2​,…,aN​。

输入保证所有测试用例的 NN 之和不超过 106106。

输出格式

对于每一个测试用例输出一行，包含字典序最大的 bb。

输入输出样例 #1

输入 #1

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

Copy

输出 #1

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

Copy

说明/提示

样例 1 解释：

在第一个测试用例中，FJ 可以将第五头奶牛移动到第二头奶牛之后。现在，a=[4,3,3,2,1]a=[4,3,3,2,1]。可以证明，[4,3,3,2,1][4,3,3,2,1] 也是字典序最大的 bb。

在第二个测试用例中，FJ 可以将第四头奶牛移动到队伍的最前面。

在第三个测试用例中，FJ 不需要执行任何操作。他可以通过将除第二头奶牛之外的每头奶牛添加到 bb 的最后来构造 bb。可以证明，这得到了字典序最大的 bb。

• 测试点 2∼42∼4：N≤100N≤100。
• 测试点 5∼85∼8：N≤750N≤750。
• 测试点 9∼189∼18：没有额外限制。

脚注

我们知道，序列 ss 的字典序大于序列 tt 当且仅当以下条件之一成立：

• 在 si≠tisi​=ti​ 的第一个位置 ii 处，有 si>tisi​>ti​。
• 当不存在这样的 ii 时，ss 的长度大于 tt。

思路

直接暴力即可。

代码见下

#include<bits/stdc++.h> 
using namespace std;
long long tt,n,a[200005],ma[200005],cc[22],c[200005][22][2],s[200005],t[200005],m[200005],lj[200005],rs[200005],fw,op=0,qp,ff,dd;
int main(){
    cin>>tt;
    while(tt--){
        cin>>n;
        op=0;
        qp=0;
        fw=0;
        ff=0;
        for(int i=0;i<=200001;i++){
            s[i]=0;
            ma[i]=0;
            t[i]=0;
            lj[i]=0;
        }        
    	for(int i=0;i<=20;i++){
    		for(int j=1;j<=n;j++){
                c[j][i][1]=c[j][i][0]=0;
            }
        }
        for(int i=1;i<=n;i++){
            cin>>a[i];
            s[a[i]]++;
            t[a[i]]=s[a[i]];
            m[a[i]]=ma[a[i]];
            ma[a[i]]=i;
    		c[i][0][0]=a[i];
    		c[i][0][1]=a[i];
        }
    	cc[0]=1;
    	for(int i=1;i<=20;i++){
    		cc[i]=cc[i-1]*2;
    	}
    	for(int i=1;i<=20;i++){
    		for(int j=1;j<=n;j++){
    			c[j][i][0]=c[j][i-1][0];
    			c[j][i][1]=c[j][i-1][1];
    			if(j+cc[i-1]<=n){
    				c[j][i][0]=max(c[j][i][0],c[j+cc[i-1]][i-1][0]);		
    			}
    			if(j-cc[i-1]>=1){
    				c[j][i][1]=max(c[j][i][1],c[j-cc[i-1]][i-1][1]);		
    			}
    		}
    	}
        for(int i=n;i>=1;i--){
            lj[i]=lj[i+1]+s[i];
        }
        for(int i=n;i>=1;i--){
            if(s[i]>=1){
                long long hj1,hj2;
                if(s[i]==1){
                    hj1=log2(ma[i]-1);
                    hj2=log2(n-ma[i]);
                    if((max(c[ma[i]-1][hj1][1],c[1][hj1][0])>=max(c[ma[i]+1][hj2][0],c[n][hj2][1])&&ma[i]!=1)||ma[i]==n){
                        op=1;
                        ff=1;
                    }
                    else{
                        op=0;
                        ff=ma[i]+1;
                    }
                }
                else{
                    hj1=log2(ma[i]-m[i]-1-1);
                    hj2=log2(n-ma[i]);
                    if((max(c[ma[i]-1][hj1][1],c[m[i]+1][hj1][0])>=max(c[ma[i]+1][hj2][0],c[n][hj2][1])&&m[i]!=ma[i]-1)||ma[i]==n){
                        op=1;
                        ff=m[i]+1;
                    }
                    else{
                        op=0;
                        ff=ma[i]+1;
                    }
                }
                if(op==1){
                    t[i]--;
                }
                for(int j=1;j<=s[i];j++){
                    cout<<i<<" ";
                }
                break;
            }
        }
        for(int i=1;i<=ff-1;i++){
            t[a[i]]--;
        }
        for(int i=n;i>=1;i--){
            if(op==1){
                //cout<<endl<<"dddddd"<<ff<<endl;
                break;
            }
            dd=ff;
            if(t[i]>=1){
                long long hj1,hj2;
                if(t[i]==1){
                    hj1=log2(ma[i]-ff-1);
                    hj2=log2(n-ma[i]-1);
                    if((max(c[ma[i]-1][hj1][1],c[ff][hj1][0])>=max(c[ma[i]+1][hj2][0],c[n][hj2][1])&&ma[i]!=ff)||ma[i]==n){
                        op=1;
                        ff=ff;
                    }
                    else{
                        op=0;
                        ff=ma[i]+1;
                    }
                    //cout<<i<<" "<<op<<" "<<ma[96]<<" "<<ff<<" "<<ma[i]-1<<endl;
                }
                else{
                    hj1=log2(ma[i]-m[i]-1-1);
                    hj2=log2(n-ma[i]);
                    if((max(c[ma[i]-1][hj1][1],c[m[i]+1][hj1][0])>=max(c[ma[i]+1][hj2][0],c[n][hj2][1])&&m[i]!=ma[i]-1)||ma[i]==n){
                        op=1;
                        ff=m[i]+1;
                    }
                    else{
                        op=0;
                        ff=ma[i]+1;
                    }
                    //cout<<max(c[ma[i]+1][hj2][0],c[n][hj2][1])<<endl;
                }
                for(int j=1;j<=t[i];j++){
                    cout<<i<<" ";
                }
                if(op==1){
                    t[i]--;
                }
            }  
            for(int i=dd;i<=ff-1;i++){
                t[a[i]]--;
            }
            if(op==1){
                //cout<<ff<<endl;
                break;
            }
        }
        if(op==1){
            for(int i=n;i>=1;i--){
                dd=ff;
                if(t[i]>=1){
                    for(int j=1;j<=t[i];j++){
                        cout<<i<<" ";
                    }
                    ff=ma[i]+1;
                }  
                for(int i=dd;i<=ff-1;i++){
                    t[a[i]]--;
                }
                //cout<<ff<<endl;
            }
        }
        cout<<endl;
    }
    // srand(time(0));
    // cout<<20<<endl;
    // for(int wf=1;wf<=20;wf++){
    //     cout<<100<<endl;
    //     for(int i=1;i<=100;i++){
    //         cout<<rand()%100+1<<" ";
    //     }
    //     cout<<endl;        
    // }
	return 0; 	
}