「AHOI2013」联通图-线段树分治+并查集

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

集合间的询问相互独立。

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

「FJOI2015」火星商店问题-线段树分治+可持久化Trie

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

「SPOJ26374」QTREE5-LCT

你被给定一棵 $n$ 个点的树,点从 $1$ 到 $n$ 编号。每个点可能有两种颜色:黑或白。我们定义 $dist(a,b)$ 为点 $a$ 至点 $b$ 路径上的边个数。一开始所有的点都是黑色的。

要求作以下操作:

  • 0 i 将点 $i$ 的颜色反转(黑变白,白变黑)
  • 1 v 询问 $dist(u,v)$ 的最小值。$u$ 点必须为白色( $u$ 与 $v$ 可以相同),显然如果 $v$ 是白点,查询得到的值一定是 $0$ 。

特别地,如果作 1 操作时树上没有白点,输出 $-1$ 。

「SPOJ16580」QTREE7-LCT

一棵树,每个点初始有个点权和颜色(输入会给你)

  • 0 u : 询问所有 $u,v$ 路径上的最大点权,要满足 $u,v$ 路径上所有点的颜色都相同
  • 1 u : 反转 $u$ 的颜色
  • 2 u w :把 $u$ 的点权改成 $w$

「SPOJ16549」QTREE6-LCT

给你一棵 $n$ 个点的树,编号 $1$~$n$ 。每个点可以是黑色,可以是白色。初始时所有点都是黑色。有两种操作:

  • 0 u :询问有多少个节点 $v$ 满足路径 $u$ 到 $v$ 上所有节点(包括端点)都拥有相同的颜色
  • 1 u :翻转 $u$ 的颜色

「SPOJ913」QTREE2-LCT

给定一棵 $n$ 个点的树,边具有边权。要求作以下操作:

  • DIST a b 询问点 $a$ 至点 $b$ 路径上的边权之和

  • KTH a b k 询问点 $a$ 至点 $b$ 有向路径上的第k个点的编号

有多组测试数据,每组数据以 DONE 结尾。

「SPOJ375」QTREE1-LCT

给定 $n$ 个点的树,边按输入顺序编号为 $1,2,…,n-1$,要求作以下操作:

  • CHANGE i v :将第 $i$ 条边权值改为 $v$
  • QUERY a b :询问从 $a$ 点到 $b$ 点路径上的最大边权

有多组测试数据,每组数据以 DONE 结尾。

「SPOJ2666」QTREE4-LCT

你被给定一棵 $n$ 个点的带边权的树(边权可以为负)。每个点可能有两种颜色:黑或白。我们定义 $dist(a,b)$ 为点 $a$ 至点 $b$ 路径上的边权值之和。一开始所有的点都是白色的。

要求作以下操作:

  • C a 将点a的颜色反转(黑变白,白变黑)

  • A 询问 $dist(a,b)$ 的最大值。$a,b$ 点都必须为白色( $a$ 与 $b$ 可以相同),显然如果树上仍存在白点,查询得到的值一定是个非负数。
    特别地,如果进行 A 操作时树上没有白点,输出 They have disappeared.

「BJOI2014」大融合-LCT

小强要在 $N$ 个孤立的星球上建立起一套通信系统。这套通信系统就是连接 $N$ 个点的一个树。 这个树的边是一条一条添加上去的。在某个时刻,一条边的负载就是它所在的当前能够 联通的树上路过它的简单路径的数量。

现在,你的任务就是随着边的添加,动态的回答小强对于某些边的负载的询问。

Your browser is out-of-date!

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

×