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

KTT

解决问题:

给定 \(n\) 个一次函数 \(y=k_ix_i+b_i\) 要支持一下操作:

  1. \(i\in [l,r],\;x_i\to x_i+p\)
  2. \(i\in [l,r],\;b_i\to b_i+w\)
  3. 查询 \(\max_{i=l}^{r} kx_i+b_i\)

其中满足 \(p \ge 0\)


发现如果只有 2,3 操作就是简单题了。

加上 1 操作的话就需要 KTT (Kinetic tournament tree) 来维护,KTT 就是线段树的一个变种。

1 操作不好维护的原因是因为每个位置增加的值不同,最大值位置可能发生改变,线段树每个节点在正常维护 \(l,r,mx\) 的基础上多维护一个 \(itr,b\) (交替阈值,区间最大值所取的函数所对斜率),表示这整个区间至少加多少后区间最大值位置会有变化,以这题为例 \(itr=\min\{ls_{itr},rs_{itr},\frac{ls_{mx}-rs_{mx}}{ls_{b}-rs_{b}}\}\) 线段树修改时,对于区间 \([l,r]\)\(d\) 则让其 \(itr\to itr-d\)。若此时 \(itr\leq 0\) 则暴力将该子树所有标记下放直至遇到 \(itr>0\) 的节点。

时间复杂度在 EI 的文章 中有详细的讲解。

KTT 解决的问题需满足函数 \(x\) 增值均为正或均为负。


考虑几个问题:

旅行规划(弱化)

给定一个长为 \(n\) 的序列,支持两种操作:

  1. 区间加等差数列( \(a,a+p,a+2p\) )。
  2. 查询区间最大值。

其中保证等差数列中任意元素均大于 0。

让序列第 \(i\)\(k_i=i\) 即可转化为第一个问题,每次操作拆分成:

\(i\in [l,r],\; x_i+p\)

\(i\in [l,r],\; b_i-(l-1)p\)

查询与第一个问题相同。

EI 的第六分块

给定一个长为 \(n\) 的序列,支持两种操作:

  1. 区间加。
  2. 查询区间最大子段和。

根据小白逛公园的思想,区间 \([l,r]\) 维护 \(lx,rx,mx\) 分别表示必须包含左或右端点的最大子段和,当前整个区间的最大子段和。

每个节点维护三个函数 \(y=kx+b\) 表示区间三种最大子段和,\(k\) 为三种最大子段和所对子段的长度。\(b\) 为三种最大子段和当前的和。\([l,r]\)\(d\),相当于 \(x\to x+d\)\(itr\) 要考虑三种最大子段和每一种的更新。

有一个需要注意,在取到最大子段和的前提下要使长度尽量长 (斜率越大增长越快)。

P6792 区间加

跟 EI 的第六分块基本一致,吉司机线段树 + KTT,把 EI 的第六分块中的 \(y=kx+b\)\(k\) 改为最大子段和所对子段中包含区间最小值的个数即可。

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

相关文章:

  • AT_joisc2021_c フードコート (Foodcourt)
  • SPP question regarding Issues Due To Gaming Spoofers
  • 类型安全ORM的高并发场景解决方案 - 实践
  • L06_mybatis读取MySQL数据库(懵逼版)
  • 提供给第三方接口的验证方法
  • 【2025最新】6款免费DLL修复工具推荐:彻底解决“XXX.dll缺失”问题!
  • 2025 年注浆管生产厂家最新推荐排行榜:聚焦 0.3mm 精度与国企合作案例,助力基建企业精准挑选优质供应商
  • 2025 年试验箱厂家 TOP 企业品牌推荐排行榜,氙灯老化 / 紫外老化 / 冷热冲击 / 恒温恒湿 / 高低温 / 快速温变 / 盐水喷雾 / 高温老化 / 砂尘 / 淋雨试验箱公司推荐!
  • 系统修复
  • 什么是vibe ?
  • 2025年10月试验箱厂家最新推荐排行榜:氙灯老化试验箱,紫外老化试验箱,冷热冲击试验箱,恒温恒湿试验箱公司推荐!
  • AI时代我们需要更多开发者:Shalini Kurapati的技术洞察
  • 新一代虚拟助手AI技术挑战赛启动
  • CSS各种选择器
  • adobe illustrator中鼠标拖动移动幅度大
  • python的字符串方法示例
  • 经典视觉跟踪算法的MATLAB实现
  • aardio 调用vb函数
  • 2025年玻璃杯趋势:某某科技圆润咖啡杯引领健康饮水新潮流
  • 2025 年密封线优质厂家最新推荐榜:权威甄选螺纹、高强度等多类型密封线质量与技术双优企业液态/亚麻/防腐/耐高温密封线厂家推荐
  • 微算法科技(MLGO)发布隐私与能量感知联盟博弈算法,重塑边缘摄像头网络架构,推动物联网智能演进
  • adobe illustrator中设置键盘增量
  • 焦虑
  • 从此,不再开口就紧张
  • 基于Qt实现百度地图路径规划功能
  • 求职,从大一开始
  • 基于C#的湿度上位机实现方案
  • 2025 年珠澳宠物托运公司联系方式推荐:爱宠国际,港澳内地宠物运输的安全专业之选
  • 男人要懂心理学
  • 斩获双项第一,天翼云问鼎中国医学影像云解决方案市场!