题解：P5537 【XR-3】系统设计

题意

给定一颗有根树和一个序列 a。对于每个询问，要么对序列 a 进行单点修改，要么给定树上的一个起点 x 和左右端点 l, r。表示从 l 开始，逐个枚举 i 直到 r，表示从目前所在的点走向儿子中编号第 a_i 小的点，走不动则结束，问最终所在的点是哪一个。

做法

先不考虑修改。

由于对 i 的枚举过程可能会中断，且 i 的合法性单调，因此改为对 i 二分，求最大合法右端点。

现在问题转化为，以给定点为起点，按照给定的与编号大小有关的特定路径走，求终点，路径不存在则返回 0。

从根走到给定起点的路径唯一，所以询问的起点不必是询问的给定点，而是根。

还是对结论“从根走到某个点的路径唯一”进行研究，反过来想。对于每个点，路径是何时答案为自己，深搜即可求解。对于原问题的询问给定的路径，需要找到哪个点对应的路径与其相同，显然哈希。

所以，对于不带修版本，做法为跑一次搜索，把每个点从根开始的路径哈希值扔到关联容器即可。

现在考虑修改序列 a，修改操作与上文在树上的做法独立，不用去考虑上文做法。

新抽象出来的问题为给定一个序列，单点修改，求区间哈希值。

哈希可以合并，扔到线段树上就做完了。