可持续字典树 Perfect Security
2024-09-18 01:30:02
题目大意:给你两个序列,第二个序列可以任意进行排列变换,然后由这两个序列一一异或得到答案序列,要求答案序列的字典序最小。
可持续字典树与第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("");
}
最新文章
- Baskets of Gold Coins_暴力
- Java递归算法——汉诺塔问题
- debug note-- nginx php-fpm : Error:The page you are looking for is temporarily unavailable.
- 《深入理解计算机系统》深入实践之——vim深入研究
- safari的坑
- RETINA显示屏下ICON优化方法
- robotframework笔记15
- 分析一下FastDFS_java_client中TestClient.java这个文件以及跟它关联的这条线
- 20160416--javaweb之国际化
- [IoLanguage]Io Tutorial[转]
- Linux shell编程02 shell程序的执行 及文件权限
- Oracle 10g的空间管理
- iOS----------适配iOS12
- python自动启动appium服务
- Java线程的创建及启动
- vba data to input tool
- mysql操作数据表中的记录1
- vscode c++ 编译生成后,调试时无法命中断点
- Python-str-操作-6
- 【codevs1004】四子连棋 状压bfs
热门文章
- Java阻塞队列四组API介绍
- Vue.js中scoped引发的CSS作用域探讨
- Markdown中希腊字母与代码对应表
- CF思维联系– CodeForces - 991C Candies(二分)
- 2019-2020 ICPC, Asia Jakarta Regional Contest C. Even Path(思维)
- CentOS启用iptables防火墙
- Java实现通过反射获取指定类的所有信息
- OKR新手入门指南 (第一部分)
- D. Misha, Grisha and Underground 树链剖分
- 带你看看Java的锁(一)-ReentrantLock