社区讨论

这题是否可以有与树剖无关的做法

ddjq_cpp
P4211[LNOI2014] LCA参与者 4已保存回复 3

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
3 条
当前快照
1 份
快照标识符
@mi6nqgs7
此快照首次捕获于
2025/11/20 07:52
4 个月前
此快照最后确认于
2025/11/20 07:52
4 个月前
查看原帖
首先，记录DFS序，将LCA（及dep[LCA]）转化为RMQ（时间复杂度 O(N)）；
将查询[l, r, z]转化为[1, r, z] - [1, l - 1, z]。
接下来，我们由左至右扫描一遍：令当前扫描到的节点为v，我们需要维护：
  • 对于任意z, 查询[1, v, z]的返回值 也就是说，我们需要一个支持如下操作的数据结构：
  • 给定一个常量数组a[]和初始值为0的cnt[]；
  • modify(x): 对于所有1 <= i <= n， 令cnt[i] += RMQ(i, x)
  • query(x): 求cnt[x]的值
考虑分块。每一块内部的cnt[]值有三种来源：
  • 左侧的modify
  • 右侧的modify
  • 块内的modify
对于前两种，各开一个set维护；对于第三种，直接暴力维护。
不妨设每一块的大小为C，则进行modify操作时，需要：
  • 暴力修改当前块的信息
  • 修改其余所有块一侧的set
可以预处理出每一块的RMQ。时间复杂度：O(C + (N / C) log(Q))
类似地，query操作需要：
  • 直接引用当前块内部的cnt[]值
  • 查询当前块两侧set中 <= 块内前缀（或后缀）RMQ的元素之和及大于它的元素个数
后者的复杂度似乎是O(C + Q log(Q))的，但注意到我们可以预处理块内前后缀的RMQ并使用手写平衡树/trie代替set从而直接维护区间和/区间个数。因此，时间复杂度为：O(log(Q))（注意trie空间开销较大）
空间复杂度：O(N + Q sqrt(N))
总时间复杂度：O(N + Q(C + (N / C) log(Q)))；取C=sqrt(N log(Q))，此时总复杂度为O(N + Q sqrt(N log(Q)))

回复

共 3 条回复，欢迎继续交流。

正在加载回复...