理解置换的概念以及题意后，剩下的就是模拟了。
花了挺长时间，主要是模拟有漏洞+想暴力过。
希望自己能养成一个做题目的好习惯，虽然写完代码再来debug能比较稳定地查出错误，但是一旦出现了整体性的解法错误就得推倒重来，这会花掉非常多的时间，希望自己能权衡一下写代码和想明白之间的时间分配，任何基本功都是值得坚持训练的。
代码
#include<stdio.h> #include<algorithm> #define m ((l+r)>>1) #define ls (now<<1) #define rs (ls|1) using namespace std; const int maxn = 100010; int n; int a[maxn]; int p[maxn]; int bar[maxn]; int nex[maxn]; int MAXBAR; int tree1[maxn<<2][2]; int tree2[maxn<<2]; void maintain2(int now) { tree2[now]=max(tree2[ls],tree2[rs]); } void build(int l,int r,int now) { tree1[now][0]=tree1[now][1]=0; if(l==r) { tree2[now]=a[l]; return; } build(l,m,ls); build(m+1,r,rs); maintain2(now); } void pushdown1(int now) { tree1[ls][1]=max(tree1[ls][1],tree1[now][1]); tree1[rs][1]=max(tree1[rs][1],tree1[now][1]); tree1[ls][0]=max(tree1[ls][0],tree1[ls][1]); tree1[rs][0]=max(tree1[rs][0],tree1[rs][1]); } void update1(int l,int r,int now,int ql,int qr,int val) { if(l>qr||r<ql) return; if(ql<=l&&r<=qr) { tree1[now][0]=max(tree1[now][0],val); tree1[now][1]=max(tree1[now][1],val); return; } pushdown1(now); update1(l,m,ls,ql,qr,val); update1(m+1,r,rs,ql,qr,val); } int qry1(int l,int r,int now,int pos) { if(l==r) return tree1[now][0]; pushdown1(now); if(pos<=m) return qry1(l,m,ls,pos); else return qry1(m+1,r,rs,pos); } void update2(int l,int r,int now,int pos) { if(l==r) { tree2[now]=0; return; } if(pos<=m) update2(l,m,ls,pos); else update2(m+1,r,rs,pos); maintain2(now); } int qry2(int l,int r,int now,int ql,int qr) { if(l>qr||r<ql) return 0; if(ql<=l&&r<=qr) return tree2[now]; return max(qry2(l,m,ls,ql,qr),qry2(m+1,r,rs,ql,qr)); } void init() { scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",a+i); p[a[i]]=i; bar[i]=0; nex[i]=0; } MAXBAR=0; build(1,n,1); } int GETMAX(int pos) { int L = qry1(1,n,1,pos); return qry2(1,n,1,L+1,pos); } void add(int L,int R) { for(int i=0;i<R-L+1;i++) { int j = (i+1)%(R-L+1); bar[L+i]=-1; nex[a[i+L]]=a[j+L]; } MAXBAR=max(MAXBAR,R); update1(1,n,1,R+1,n,R); bar[R]=1; bar[L-1]=1; } void print() { for(int i=1;i<=n;i++) printf("%d%c",nex[i],i==n?'\n':' '); } void solve() { init(); for(int i=1;i<=n;i++) if(!nex[i]) { a[n+1]=a[MAXBAR+1]; int PMAX = GETMAX(p[i]); int NMAX = bar[p[i]]==1?0:a[p[i]+1]; if(PMAX>=NMAX) add(p[PMAX],p[i]); else { update2(1,n,1,p[i]+1); bar[p[i]]=-1; nex[i]=a[p[i]+1]; } } print(); } int main() { int T; scanf("%d",&T); while(T--) solve(); return 0; }