avatar
文章
83
标签
20
分类
13
首页
标签
分类
友链
关于
wjyppm's Blog路线反思 返回首页
搜索
首页
标签
分类
友链
关于

路线反思

发表于2025-09-28|更新于2025-09-28|笔记
|总字数:9|阅读时长:1分钟|浏览量:
路线反思
https://worldcpu.github.io/posts/a6ad8815/
作者
wjyppm
发布于
2025-09-28
更新于
2025-09-28
许可协议
CC BY-NC-SA 4.0
cover of next post
下一篇
猫树分治
猫树，整体二分与线段树分治的结合，前者我快忘了，后者更是学都没学过 www。 说人话，就是一种不支持修改，仅仅支持快速区间询问的一种静态线段树。构造要执行 O(nlog⁡n)O(n\log n)O(nlogn) 次合并操作，而查询可以加速到 O(1)O(1)O(1) 次合并操作。 猫树问题可以适用于离线解决以下类型的数据结构问题： 与序列有关，且询问是一段区间。 序列静态，即，不涉及修改操作。 当然离不离线都可以，由于其过程类似于点分治，所以在线的情况可通过类似于建出建出点分治的情况动态维护。 我们通过一道例题来进行引入： 给你一个长为 nnn 的序列 aaa，有 qqq 次询问，每次询问区间 [l,r][l,r][l,r] 的最大值和最大值个数，可以离线。 1≤n≤2×105,1≤q≤7×106,1≤l≤r≤n,1≤ai≤1091\le n\le 2\times 10^5,1\le q \le 7\times 10^6,1\le l\le r\le n,1\le a_{i}\le 10^91≤n≤2×105,1≤q≤7×106,1≤l≤r≤n,1≤ai​≤109。 显然...
评论
avatar
wjyppm
高中蒟蒻信竟生
文章
83
标签
20
分类
13
Follow Me
公告
👋🏻我是PPM，一个热爱编程和信息学竞赛的高中生，喜欢分享做题经验。本博客中所有 latex 公式均可以选中后复制哦😊

❓有问题欢迎提问，确保内容有意义。如需联系我，欢迎通过邮箱联系我！📧

嗷嗷！热烈欢迎🤪！来自

的朋友，你好呀！
你的网络IP为：***.***.***.***

目录
  1. 1. 前言报告
  2. 2. 回顾
    1. 2.1. 基础知识点的补充以及经验不足
    2. 2.2. 路线偏差与工具的介入
    3. 2.3. 功利化的路线行进与幻想破灭
  3. 3. 问题分析
    1. 3.1. 比赛经验和方法
    2. 3.2. 做题方法
    3. 3.3. 总结方法
    4. 3.4. 路线问题
  4. 4. 总结
最新文章
路线反思
路线反思2025-09-28
猫树分治
猫树分治2025-09-21
MatrixTree矩阵树定理
MatrixTree矩阵树定理2025-09-17
abc423题解
abc423题解2025-09-15
整体DP—从勤拿少取到量大管饱
整体DP—从勤拿少取到量大管饱2025-09-12
© 2025 By wjyppm框架 Hexo 7.3.0|主题 Butterfly 5.4.3
搜索
数据加载中