题解

很容易求出在没有字典序最大的限制条件下的最多胜利场数。

这样就可以对于每一位放最优的解,怎么做,二分答案。

分两种情况,一种是当前一位是输的,一种是赢的,复杂度 \(\mathcal O(\rm nlog^2n)\) 卡卡常即可。

Code
#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();}

最新文章

  1. 关于IIS服务器证书续订
  2. iOS关于TableViewController和CollectionViewController中self.view心得记录
  3. opencv的学习笔记1
  4. linux -小记(2)问题:yum 安装报错&quot;Another app is currently holding the yum lock; waiting for it to exit... ...: yum Memory : 26 M RSS (868 MB VSZ) Started: Wed Oct 26 22:48:24 2016 - 0&quot;
  5. Atom使用心得 - 21世纪的编辑器
  6. Spark自定义分区(Partitioner)
  7. C#接收post数据
  8. iOS 中Window优先级的问题
  9. OCP-1Z0-051-题目解析-第6题
  10. jQuery中对 input 控件的操作
  11. photoshop移动工具
  12. C++入门程序作业1
  13. Python lambda介绍
  14. InstallUtil操作WindowsService
  15. Unity3D架构设计NavMesh寻路
  16. lazarus的动态方法和虚拟方法
  17. BZOJ2958 序列染色
  18. JDK1.7配置及测试
  19. (转)使用PowerDesigner生成HTML功能
  20. linux systemctl service examples

热门文章

  1. 第九章 身体质量指数BMI的python实现
  2. 「CF521D」 Shop
  3. C语言:FILE p和FILE *p
  4. DEV -C++源码中的中文复制粘贴乱码解决方案
  5. python mysql 类 图片保存到表中,从表中读图片形成图片文件
  6. 解决远程连接服务器数据库报错:Host ‘XXXXXX’ is blocked because of many connection errors
  7. 前端之html基础演示
  8. linux下系统时间和时钟时间
  9. oracle 密码详解以及破解
  10. Cesium加载地形数据只显示半个地球