很容易求出在没有字典序最大的限制条件下的最多胜利场数。
这样就可以对于每一位放最优的解,怎么做,二分答案。
分两种情况,一种是当前一位是输的,一种是赢的,复杂度 \(\mathcal O(\rm nlog^2n)\) 卡卡常即可。
#include<bits/stdc++.h> #define ri register signed #define p(i) ++i namespace IO{ char buf[1<<21],*p1=buf,*p2=buf; #define gc() p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?(-1):*p1++ struct nanfeng_stream{ template<typename T>inline nanfeng_stream &operator>>(T &x) { ri f=1;x=0;register char ch=gc(); while(!isdigit(ch)) {if (ch=='-') f=0;ch=gc();} while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=gc();} return x=f?x:-x,*this; } }cin; } using IO::cin; namespace nanfeng{ #define FI FILE *IN #define FO FILE *OUT template<typename T>inline T cmax(T x,T y) {return x>y?x:y;} template<typename T>inline T cmin(T x,T y) {return x>y?y:x;} static const int N=1e5+7; int an[N],bn[N],tmx[N],tx,n,mx; struct ZKW{ #define ls(x) (x<<1) #define rs(x) (x<<1|1) struct segmenttree{int s,a,b;}T[N<<3]; int bs; ZKW() {bs=1;} inline void up(int x) { int tmp=cmin(T[ls(x)].b,T[rs(x)].a); T[x].s=T[ls(x)].s+T[rs(x)].s+tmp; T[x].a=T[ls(x)].a+T[rs(x)].a-tmp; T[x].b=T[ls(x)].b+T[rs(x)].b-tmp; } inline void build() {for (;bs<=mx;bs<<=1);} inline void update(int p,int x,int t) { p+=bs; if (t) T[p].b+=x; else T[p].a+=x; for (p>>=1;p;p>>=1) up(p); } }T; inline int main() { //FI=freopen("nanfeng.in","r",stdin); //FO=freopen("nanfeng.out","w",stdout); cin >> n; for (ri i(1);i<=n;p(i)) cin >> bn[i],mx=cmax(mx,bn[i]); for (ri i(1);i<=n;p(i)) cin >> an[i],mx=cmax(mx,an[i]),p(tmx[an[i]]); tx=mx; T.build(); for (ri i(1);i<=n;p(i)) T.update(bn[i],1,1),T.update(an[i],1,0); int ans=T.T[1].s; for (ri i(1);i<=n;p(i)) { T.update(bn[i],-1,1); ri l=bn[i]+1,r,res(-1); while(!tmx[tx]) --tx; r=tx; while(l<=r) { int mid(l+r>>1); T.update(mid,-1,0); if (T.T[1].s==ans-1) l=mid+1,res=mid; else r=mid-1; T.update(mid,1,0); } if (res!=-1) --ans,--tmx[res],printf("%d ",res),T.update(res,-1,0); else { l=1,r=bn[i],res; while(l<=r) { int mid(l+r>>1); T.update(mid,-1,0); if (T.T[1].s==ans) l=mid+1,res=mid; else r=mid-1; T.update(mid,1,0); } T.update(res,-1,0); printf("%d ",res); --tmx[res]; } } puts(""); return 0; } } int main() {return nanfeng::main();}