rprp

图论

动态规划(12) 字符串(3) 搜索(1) 数学(6) 数据结构(18) 未归档(2) 贪心(5) 配置(2)

/ 注册

全部文章 / 图论（共1篇）

Luogu P3292 [SCOI2016]幸运数字

看到异或最值，显然想到线性基。用树上倍增的方法，维护当前点\(x\)到倍增父节点\(fa[x][i]\)这条路径上的线性基，在倍增的时候暴力合并即可。注意这个线性基的倍增数组是没有包括最后一个点的信息的，需要特殊处理。然后就搞完了。时间复杂度\(O(n*log_n*log_v+q*log_n*...

倍增线性基

2020-05-03

0 379