线段树分治
「AHOI2013」联通图-线段树分治+并查集
· ✏️ 748 words · ☕ 2 mins read

给定一个 n 个点 m 条边的无向连通图 G 和若干个小集合 S,每个小集合包含 c(1c4) 条边,对于每个集合,你需要确定将集合中的边删掉后改图是否保持联通。

集合间的询问相互独立。


「HAOI2017」八纵八横-线段树分治+线性基
· ✏️ 1518 words · ☕ 4 mins read

Anihc 国有 n 个城市,这 n 个城市从 1 ~ n 编号,1 号城市为首都。城市间初始时有 m 条高速公路,每条高速公路都有一个非负整数的经济影响因子,每条高速公路的两端都是城市(可能两端是同一个城市),保证任意两个城市都可以通过高速公路互达。

Anihc 国正在筹划「八纵八横」的高铁建设计划,计划要修建一些高速铁路,每条高速铁路两端也都是城市(可能两端是同一个城市),也都有一个非负整数的经济影响因子。国家还计划在「八纵八横」计划建成之后,将「一带一路」扩展为「一带一路一环」,增加「内陆城市经济环」即选择一条从首都出发沿若一系列高铁与高速公路走的路径,每条高铁或高速公路可以经过多次,每座城市也可以经过多次,最后路径又在首都结束。令「内陆城市经济环」的 GDP 为依次将这条路径上所经过的高铁或高速公路的经济影响因子异或起来(一条路经过多次则会被计算多次)。

现在 Anihc 在会议上讨论「八纵八横」的建设计划方案,他们会不断地修改计划方案,希望你能实时反馈对于当前的「八纵八横」的建设计划的方案「内陆城市经济环」的最大是多少。

初始时,八纵八横计划中不包含任何—条高铁,有以下三种操作:

  • Add x y z :在计划中给在城市 x 和城市 y 之间建设一条高铁,其经济影响因子为 z ,如果这是第 k 个 Add 操作,则将这条高铁命名为 k 号高铁。

  • Cancel k :将计划中的 k 号高铁取消掉,保证此时 k 号高铁一定存在。

  • Change k z :表示将第 k 号高铁的经济影响因子更改为 z ,保证此时 k 号高铁一定存在。


「FJOI2015」火星商店问题-线段树分治+可持久化Trie
· ✏️ 1075 words · ☕ 3 mins read

n 个商店,每个商店都有一个特殊商品,每个人在任何时间都可以买。第一天可能没有进货,有若干次询问,而之后的每天,都有一次进货和若干次询问,每次进货都是某个商店进了某个编号的货,每次询问都是询问在编号为 lr 的商店中,在 d 天内进的货的编号异或 x 的最大值。