【2018icpc Dhaka G】Techland 题解

题目大意

  有一棵 $n$n 个点的树，点编号 $1$1~$n$n。有 $Q$Q 次操作，操作有三种类型：
  $1~X~L~R$1 X L R：公司 $X$X 在编号属于 $[L,R]$[L,R] 的点上各开一家商店。如果该公司曾经有过商店，则它以前的商店全部清除，只算这次的。
  $2~X$2 X：公司 $X$X 的商店全部清除。
  $3~C~M~P_1~P_2~...~P_M$3 C M P1​ P2​ ... PM​：有个人在 $C$C 号点，他指定了他喜欢的公司为 $P_1$P1​~$P_M$PM​，你要找到一个离 $C$C 最近的点，使得这个点有他喜欢的公司开的商店。求这个距离。

  单组数据：$n \leq 50000,~Q \leq 10^5,~\sum m \leq 10^5$n≤50000, Q≤105, ∑m≤105
  10 组数据共 10s。

$\\$
$\\$
$\\$

题解

对了…上次那个 G 题，我后来想了想发现是个点分水题.
——liyang21

  由于 $\sum m \leq 10^5$∑m≤105，只需要对于每个 $P_i$Pi​，求 $C$C 点到相应的 $[L_i,R_i]$[Li​,Ri​] 这些点的最短距离就好了。

  你想，要是每个点 $x$x 有一棵线段树，记录着 $x$x 到所有点的最短距离，那就好了，就可以对于每个询问直接区间查询 $[L_i,R_i]$[Li​,Ri​] 的最小值了。

  但这样太大了。想办法以时间换空间，我查询多一些东西，让这个线段树总量少些。

  由于最近点是经典点分题，于是想到了点分

  考虑点分树，对于每个点，只记录它的子树上的所有点到它的最短距离。你可以给点重新编号，或者用主席树，使得这个线段树总大小为 $O(n~log~n)$O(n log n)。
  这样一来，点 $x$x 到终点 $z$z 的路径就被分为了两部分，第一部分是 $x$x 到它点分树上的祖先 $y$y，第二部分是 $y$y 到 $z$z。
  因此查询的话，就从点分树的根一直查到那个点。比如上面说的我查询点 $x$x，现在考虑它点分树上的祖先 $y$y，那么就是 $dis_{x,y}+\min\{dis_{y,z}|z\in[L_i,R_i]\}$disx,y​+min{disy,z​∣z∈[Li​,Ri​]}，这就是线段树区间查询了。点分树树高为 $log~n$log n，线段树查询有一个 $log~n$log n，因此复杂度为 $O(m~log^2~n)$O(m log2 n)。

代码

\\待填坑