当前位置: 首页 > news >正文

NOIP2024

T3

还需要再琢磨琢磨。

T4

首先我们考虑一个节点 \(u\) 对答案的贡献。假设 \(u\) 子树内的数形成了若干个极大的连续段 \([l, r]\),若 \([ql, qr]\) 与某个 \([l, r]\) 的交集至少为 \(k\) 就有 \(dep_u\) 的贡献。

所以我们来考虑如何维护这个极大的连续段。一个比较显然的方式是并查集,加入一个元素 \(x\) 后,只可能将 \(x - 1, x, x + 1\) 所在的集合连到一起,只需要用 \(x\) 现在所在的集合进行贡献。

但是我们也不可能将每次将 \(u\) 内所有元素都扫一遍,那就爆了。这时我们就可以想到启发式合并,每次 \(u\)\(son_u(u 的重儿子)\) 继承过来,这样总共至多加入 \(O(n \log n)\) 的元素了。而且这样做显然是正确,因为只会漏算只包含 \(son_u\) 子树的连续段,而这个显然 \(son_u\) 贡献更优。

所以我们就拥有了 \(m(m \le n \log n)\) 个可能贡献的区间,接下来就比较好办了。对于 \(l < ql\) 的,只需要满足 \(r \ge ql + k - 1\);对于 \(l \ge ql\) 的,只需要满足 \(r - l + 1 \ge k, l \le qr - k + 1\),化简一下 \(ql \le l \le qr - k + 1 \&\& r - l + 1 \ge k\)。就是两个二维数点,搞个线段树即可在 \(O((m + q) \log m)\) 的时间内解决。

所以我们就拥有了时间复杂度最坏为 \(O(n \log^2n)\) 的做法,其实已经能过了。但是还有更优秀的做法。


对于后半部分其实没办法优化了,只能优化前半部分。我们仔细分析,只有当两个集合合并时才有会产生一个贡献区间,而总共只有 \(n\) 个数,也就是最多只有 \(O(n)\) 个有用的区间。

但是启发式合并已经没有前途了。不过也许你知道这个结论:\(dep_\text{LCA*(l, r)} = \min\limits_{i = l}^r dep_{\text{LCA(i, i + 1)}}\)。那我们可以求出所有 \(\text{Lca(i, i + 1)}\),用单调栈(笛卡尔树)求出这个它为最小值的区间,这就可以得到 \(O(n)\) 个区间了,不难发现它是包含了所有情况的。

时间复杂度来到了 \(O(n \log n)\)

评价

一条链的部分分有利于可以让我们想到使用若干个有用的贡献区间 \([l, r]\)来贡献答案。(似乎容易去想线段树上二分,而非并查集,并且容易误导人,以为新增的区间一定包含 \(u\),反正我被坑了。)

两只 \(\log\) 的做法还是比较粗暴的,单 \(\log\) 需要知道一个结论。(我想到另一个结论:找 \(dfs\) 最小和最大的算 LCA,然后没有任何前途)

似乎搞完 SA 后也一般是笛卡尔树或者并查集进行合并。

http://www.hskmm.com/?act=detail&tid=36943

相关文章:

  • 20232415 2025-2026-1 《网络与系统攻防技术》 实验二实验报告
  • 结对项目:四则运算生成器
  • CSP-S2023
  • Spring Boot 中全面解决跨域请求
  • OpenTelemetry语义约定:规范可观测性数据,提升系统洞察力
  • 拓展欧几里得算法
  • 两两交换链表中的节点-leetcode
  • 算法第二章实践作业
  • 解决homebrew下载报错问题
  • 软考中级学习总结(5)
  • 软考中级学习总结(4)
  • 每日反思(2025_10_22)
  • docker: Error response from daemon: failed to set up container networking 解决办法
  • 实验2 现代C++编程初体验
  • CSP-S36
  • 新学期每日总结(第13天)
  • GCM(Galois/Counter Mode) 认证加密算法实现
  • 【学习笔记】slope-trick
  • 10.13-10.19学习做题笔记
  • 2025.10.22
  • yny计数题记录
  • 20232404 2025-2026-2 《网络与系统攻防技术》实验二实验报告
  • 1020302118兰逸霏的第一次作业
  • ubuntu 25.10 修改源 - ldx
  • pytorch学习笔记(1)
  • 20232318 2025-2026-1 《网络与系统攻防技术》实验二实验报告
  • 《中华人民共和国网络安全法》第二十一条这一核心考点
  • 嵌入式软件分层架构设计 - lucky
  • DP 基础题乱做
  • [题解]P4616 [COCI 2017/2018 #5] Pictionary