树上莫队真好玩(
一不小心就写了 144 行(逃
首先考虑序列上的带修莫队,只要给询问加一维时间就可以了。
那么问题来了,怎么把问题放到树上?
用树剖把询问划分成几个区间。
这样子复杂度没法接受……
考虑把 DFS 序改一下,在递归到每个点和递归完每个点的时候都记录,变成括号序列。
我们定义括号序列中一段区间只有只出现了一次的数有贡献。
样例以 1 为根,得到的括号序列即 {1,3,4,4,2,2,3,1}。
设 stp 表示递归到 p 的时间戳,edp 表示递归完 p 的时间戳。
对于一个询问 x,y(stx<sty),我们分两种情况讨论:
[sty,edy]⊆[stx,edx]:
这种情况,我们只需要计算 [stx,sty] 的贡献即可。
例如样例的树中,查询 1,2,区间为 [1,5],实际有贡献的点为 1,3,2,恰好是我们想要的。[stx,edx]⋂[sty,edy]=∅:
这种情况,我们需要计算的是 [edx,sty]。
但是这样会少掉 LCA 的贡献,再加回来。
例如查询 4,2,区间为 [4,5],实际有贡献的点为 4,2,加上 LCA 即 3 的贡献就好了。
计算贡献时,可以用一个数组记录有贡献的点。
然后添加 / 删除贡献时,异或处理即可。
洛谷上开了 O2 才能过(TLE 28458ms→AC 9889ms)。
代码:
1 |
|