题目链接

题目大意:给你两个序列,第二个序列可以任意进行排列变换,然后由这两个序列一一异或得到答案序列,要求答案序列的字典序最小。

可持续字典树与第K大可持续线段树的区别主要在于每个节点上 ,它多了一个记录值。

因为线段树肯定是对区间处理,要+1的,但是字典树是对点处理,这两个值都要记录。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=3e5+;
int sum[N*][],son[N*][],x,n,tot,a[N];
void update(int last,int cur,int num,int pos){
int temp=!!(num&(<<pos));
sum[cur][temp]=sum[last][temp]+;
sum[cur][temp^]=sum[last][temp^];
son[cur][temp^]=son[last][temp^];
if(!pos) return;
update(son[last][temp],son[cur][temp]=++tot,num,pos-);
}
void query(int last,int cur,int num,int pos,int ans){
if(pos<) {printf("%d ",ans);return;}
int temp=!!(num&(<<pos));
if(sum[cur][temp]-sum[last][temp]>) --sum[cur][temp],query(son[last][temp],son[cur][temp],num,pos-,ans);
else --sum[cur][temp^],query(son[last][temp^],son[cur][temp^],num,pos-,ans|(<<pos));
}
int main(){
scanf("%d",&n);
for(int i=;i<=n;++i) scanf("%d",a+i);
scanf("%d",&x);
update(,++tot,x,);
for(int i=;i<=n;++i) {
scanf("%d",&x);
update((i-)*+,++tot,x,);
}
for(int i=;i<=n;++i) query(,(n-)*+,a[i],,);
puts("");
}

最新文章

  1. Baskets of Gold Coins_暴力
  2. Java递归算法——汉诺塔问题
  3. debug note-- nginx php-fpm : Error:The page you are looking for is temporarily unavailable.
  4. 《深入理解计算机系统》深入实践之——vim深入研究
  5. safari的坑
  6. RETINA显示屏下ICON优化方法
  7. robotframework笔记15
  8. 分析一下FastDFS_java_client中TestClient.java这个文件以及跟它关联的这条线
  9. 20160416--javaweb之国际化
  10. [IoLanguage]Io Tutorial[转]
  11. Linux shell编程02 shell程序的执行 及文件权限
  12. Oracle 10g的空间管理
  13. iOS----------适配iOS12
  14. python自动启动appium服务
  15. Java线程的创建及启动
  16. vba data to input tool
  17. mysql操作数据表中的记录1
  18. vscode c++ 编译生成后,调试时无法命中断点
  19. Python-str-操作-6
  20. 【codevs1004】四子连棋 状压bfs

热门文章

  1. Java阻塞队列四组API介绍
  2. Vue.js中scoped引发的CSS作用域探讨
  3. Markdown中希腊字母与代码对应表
  4. CF思维联系– CodeForces - 991C Candies(二分)
  5. 2019-2020 ICPC, Asia Jakarta Regional Contest C. Even Path(思维)
  6. CentOS启用iptables防火墙
  7. Java实现通过反射获取指定类的所有信息
  8. OKR新手入门指南 (第一部分)
  9. D. Misha, Grisha and Underground 树链剖分
  10. 带你看看Java的锁(一)-ReentrantLock