P8339题解

· · 题解

由于每种颜色的钥匙至多有5把，我们可以提前找出能匹配的钥匙和箱子对，这里的能匹配是指如果一个箱子和一把钥匙之间还有一把未配对的钥匙，则让箱子和中间的那把钥匙配对，因为若按原来的匹配，能包含这个匹配的查询一定能包含新的匹配。求出所有匹配的过程类似处理树上括号序列，但是对于每种颜色的每把钥匙，直接在原树上跑会超时，可以把同种颜色的点作为关键点建立虚树，在虚树上处理即可保证复杂度。 对于一把钥匙 k 和一个箱子 b ，它们能够匹配，考虑哪些查询 (s,t) 能包含这个匹配，有三种情况：

一棵子树内的点的dfs序是连续的，把 s 作为横坐标 ， t 作为纵坐标，那么每一个匹配就对应一个或两个二维平面上的矩形，每一个查询相当于平面上的一个点，问这个点被多少个矩形包含，用扫描线维护即可。