louhc

分类

未归档(78) 题解(81)

/ 注册

全部文章（共2篇）

题解 | 算法竞赛进阶指南可持久化并查集

思路说是可持久化并查集,实际上就是把并查集使用的数组变成可持久化数组.当然,可持久化并查集路径压缩不现实,这样可能总共需要修改个值,空间复杂度可能不好过去.想象当初学并查集时使用的优化,出了路径压缩,还有按秩合并.这样一次只需要修改个值,而且复杂度基本一样.这样子时间复杂度为,空间复杂度为. 代码...

并查集可持久化数据结构

2019-08-28

0 631

题解 | 算法竞赛进阶指南最大异或和

思路可持久化入门题.首先,如果不是区间,而是整体询问的话,我们可以直接建,从高位到低位枚举,答案的这一位能是1就为1,不然只能为0.区间询问的话其实相差不大.使用可持久化树,这样就知道每个前缀序列构成的树.还需要记录每个节点总共经过了几次.然后在两棵树上跑,这里判断是否有节点作差即可(类似于前缀和...

字典树可持久化数据结构

2019-08-28

1 605