维护一个当前可以插入数的set
如果当前数等于上一个数，那么字典序最大序列答案就是set最大值，取出并删除、字典序最小序列答案就是set最小值，取出并删除
如果不等，那么最大序列和最小序列这个位置的数就是该数
代码语言：javascript复制#include<bits/stdc .h>
using namespace std;
#define ll long long
const int N=2e5 10;
ll t,a[N],maxx[N],minn[N];
int main(){
cin>>t;
while(t--){
int x;
cin>>x;
set<int>t1,t2;
for(int i=1;i<=x;i )cin>>a[i];
maxx[1]=minn[1]=a[1];
for(int i=1;i<a[1];i ){
t1.insert(i);
t2.insert(i);
}
for(int i=2;i<=x;i ){
if(a[i]!=a[i-1]){
maxx[i]=minn[i]=a[i];
for(int j=a[i-1] 1;j<a[i];j ){
t1.insert(j),t2.insert(j);
}
}
else{
set<int>::iterator it=t2.end();
--it;
int res1=*t1.begin(),res2=*it;
minn[i]=res1,maxx[i]=res2;
t1.erase(res1),t2.erase(res2);
}
}
for(int i=1;i<=x;i )cout<<minn[i]<<" ";
cout<<endl;
for(int i=1;i<=x;i )cout<<maxx[i]<<" ";
cout<<endl;
}
return 0;
}
