Contest Info

date: 2019.06.22 12:35-17:35

practice link

Solutions

F. Path Intersection

题目大意：给出一棵\(n\le10000\)的树，\(q\le10000\)次询问，每次给出\(k\le50\)条路径，问它们的交集大小。

题解：求出包含路径两个点，及其lca和lca的父节点的虚树，在虚树上算一下覆盖次数统计答案即可。时间复杂度\(O(n\log{n}+\sum k\log{n})\).

G. Techland

题目大意：给出一棵\(n\le50000\)的树，\(q\le100000\)次事件，每次或者是出现公司\(x\)在区间\([l_x,r_x]\)出现，并把\(x\)之前的出现都撤销，或者是撤销公司\(x\)的出现，或者是给出点\(c\)和\(m\)个公司\(x_1,\cdots,x_m\)，问这些公司出现的点中距离\(c\)最近的距离是多少。

题解：建立点分树，在每个重心用线段树维护到重心的距离的区间最小值，公司的出现与撤销只需要维护一个数组记录即可，回答询问时访问点分树中\(c\)到根的\(\log{n}\)个重心，在线段树中查询最小值更新答案即可。时间复杂度\(O((n+\sum m)\log^2{n})\)，空间复杂度\(O(n\log^2{n})\).