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

羡慕线段树

顺颂 YFST 板子 & 使用例

题。首先树剖,然后变成在 \(\text{dfn}\) 区间上插一个关于 \(\text{dis}\) 的一次函数。这个很神奇,一般的李超树是,在 \(x\) 轴区间上插入关于 \(x\) 的一次函数。然而这里,\(\text{dfn}\)\(\text{dis}\) 看起来毫无关系。

考虑李超树运用了线段的什么性质。无外乎,单调性线性性

第一个显然,你树剖出来的 \(\text{dfn}\) 连续段是一条链,\(\text{dis}\)\(\text{dfn}\) 单调递增,那关于 \(\text{dis}\) 单调的函数自然也关于 \(\text{dfn}\) 单调。所以李超树维护的实际上是一堆折线。

有人就说,你只是在某些区间满足这个单调性,整棵树维护的东西不是乱套?管你吗的整棵树,修改查询的所有区间都合法就能满足我的要求,靠近根的那些点根本查不到。

对于线性性,它实际上是在满足这个:

if(f(ln)<g(now)(ln)) dnf(ls(now),ln,mid,f);
if(f(rn)<g(now)(rn)) dnf(rs(now),mid+1,rn,f);

就是说,如果线段 \(f\) 的两端点分别高于 \(g\),那么 \(f\) 就没有任何一处的取值比 \(g\) 小。乍一看折线好像不行:

但是这里的折线不一般。注意到 \(\text{dfn}\)\(\text{dis}\) 是一个映射,图中线段斜率 \(\text{dis}\times a\)(设关于 \(\text{dis}\) 函数的斜率是 \(a\)),那么如果折线 \(f\) 在某一处的斜率比 \(g\) 要大,\(f\) 所对应原函数的 \(a\) 也要更大,\(f\) 的斜率便永远大于 \(g\),上图相交两次的情况根本不存在。

然后注意一次函数求值要把对应的 \(\text{dis}\) 而不是 \(\text{dfn}\) 代进去就是了。

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

相关文章:

  • 质量检验知识专题讲座之七:来料检验
  • windows 10分区教程,win10自带分区教程
  • # Python 类中方法类型详解
  • 决斗(模拟赛题目T3)分析
  • 大学C语言课摸鱼记
  • gitlen中,已经提交了内容,如何回退到修改前?
  • CF1989F
  • 2025.10.10——1绿
  • Vue3水波纹指令:2025年Material Design交互新标准 - 实践
  • 巨型飞机运输风力涡轮机叶片技术解析
  • CCPC2024女生专场 游记(VP)
  • 重磅福利,JetBrains 宣布 DataGrip 面向非商业用途免费!
  • 【GitHub每日速递 251010】Zen MCP:一键 orchestrate 多 AI 模型,代码开发协作新革命!
  • 22 LCA模拟赛2T1 奶龙与贝利亚 题解
  • 微软拼音输入法自定义短语批量导入导出工具(支持Windows 10/11)
  • AI风险管控新规应对系统抵抗关闭行为
  • BLDC中的Q15
  • 华为 AP hw_manage 离线管理 Wi-Fi 密码
  • 雪落 - L
  • 251009
  • Mybatis笔记
  • PluginMonitor - Typecho 插件监控工具
  • LibreChat-图文并茂手把手教你搭建自己的AI机器人 Step-by-step guide to building your own chatbot
  • NOISG 2025 Prelim
  • STM32 教程
  • 先进反应堆:BWRX-300
  • ch58x/ch59x系列芯片Indication添加
  • Lab 4 Challenge - Sum of Proper Elements
  • perl经典hash解决问题
  • LCR 129. 字母迷宫