「SDOI2013」森林-主席树+LCA+启发式合并

小Z有一片森林,含有$N$个节点,每个节点上都有一个非负整数作为权值。初始的时候,森林中有$M$条边。

小Z希望执行$T$个操作,操作有两类:

  • Q x y k查询点$x$到点$y$路径上所有的权值中,第$k$小的权值是多少。此操作保证点$x$和点$y$连通,同时这两个节点的路径上至少有$k$个点。

  • L x y在点$x$和点$y$之间连接一条边。保证完成此操作后,仍然是一片森林。

强制在线。

对于所有的数据$n,m,T \leq 8 \times 10^4$。

「HNOI2009」梦幻布丁-set-启发式合并

$n$ 个布丁摆成一行,每个布丁最开始都有一个颜色 $c_i$ ,进行 $m$ 次操作。

操作格式:

  • 1 c d :将所有的 $c$ 颜色替换为$d$

  • 2 :查询当前布丁序列一共有多少段颜色。例如颜色分别为 $1,2,2,1$ 的四个布丁一共有3段颜色。

Your browser is out-of-date!

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

×