「HAOI2017」八纵八横-线段树分治+线性基

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$ 号高铁一定存在。

「WC2011」最大XOR路径-dfs+线性基

考虑一个边权为非负整数的无向连通图,节点编号为 $1$ 到 $N$ ,试求出一条从 $1$ 号节点到 $N$ 号节点的路径,使得路径上经过的边的权值的 $\text{XOR}$ 和最大。

路径可以重复经过某些点或边,当一条边在路径中出现了多次时,其权值在计算 $\text{XOR}$ 和时也要被计算相应多的次数。

图中可能有重边或自环。

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×