BZOJ3689 异或之
对于每对(i, j)满足1 <= i < j <= n,得到一个新的数A[i] xor A[j],这样共有n*(n-1)/2个新的数。求这些数(不包含A[i])中前k小的数。
发布日期:2022-02-07 06:39:32
浏览次数:9
分类:技术文章
本文共 1395 字,大约阅读时间需要 4 分钟。
题目大意: 给定n个非负整数A[1], A[2], ……, A[n]。对于每对(i, j)满足1 <= i < j <= n,得到一个新的数A[i] xor A[j],这样共有n*(n-1)/2个新的数。求这些数(不包含A[i])中前k小的数。
注:xor对应于pascal中的“xor”,C++中的“^”。
思路:同NOI2010超级钢琴。
我们只需一开始在全局堆中放进去每个数和他之后的数异或的最小值,然后在每次出堆的的时候再放进堆中第k+1小值即可。这样重复k次。
那么问题就变成了快速求某段区间给定一个数进行xor的第k小值,我们利用可持久化trie维护size直接在树上二分即可。
时间复杂度依旧O(klogn).
Code:
#include#include #include #include using namespace std; #define N 100010int w[N]; int ch[N<<5][2], size[N<<5], ind;int root[N];int Newadd(int Last, int bit, int x) { int q = ++ind; ch[q][0] = ch[Last][0], ch[q][1] = ch[Last][1]; size[q] = size[Last] + 1; if (bit < 0) return q; if ((x >> bit) & 1) ch[q][1] = Newadd(ch[Last][1], bit - 1, x); else ch[q][0] = Newadd(ch[Last][0], bit - 1, x); return q;}int getkth(int Left, int Right, int x, int k) { int res = 0, better; bool d; for(int dep = 30; dep >= 0; --dep) { d = (x >> dep) & 1; better = size[ch[Right][d]] - size[ch[Left][d]]; if (better >= k) Left = ch[Left][d], Right = ch[Right][d]; else Left = ch[Left][d ^ 1], Right = ch[Right][d ^ 1], res += (1< >= 1) if (a[x] >1]) swap(a[x],a[x>>1]); else break; } inline void down(int x) { int son; for(; (x<<1)<=top; ) { son=(((x<<1)==top)||(a[x<<1] <<1)|1]))?(x<<1):((x<<1)|1); if (a[son]
转载地址:https://blog.csdn.net/wyfcyx_forever/article/details/40400287 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
能坚持,总会有不一样的收获!
[***.219.124.196]2024年04月11日 17时12分51秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
Unity中的刚体
2019-04-27
Unity中的坐标转换
2019-04-27
Unity中为什么不能对transform.position.x直接赋值?
2019-04-27
Unity中物体移动方法详解
2019-04-27
使用对象池优化性能
2019-04-27
Unity中的UI方案(基础版)
2019-04-27
Lua(一)——Lua介绍
2019-04-27
Lua(二)——环境安装
2019-04-27
Unity中父子物体的坑
2019-04-27
基础知识——进位制
2019-04-27
Lua(十二)——表
2019-04-27
Lua(十三)——模块与包
2019-04-27
Lua(四)——变量
2019-04-27
Lua(十四)——元表
2019-04-27
Lua(十五)——协同程序
2019-04-27
Lua(十六)——文件
2019-04-27
Lua(十七)——面向对象
2019-04-27
Lua(十八)——错误处理,垃圾回收
2019-04-27
xLua(一)——介绍
2019-04-27
xLua(二)——下载
2019-04-27