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

[CEOI 2025] Equal Mex

静态复杂区间 mex 问题考虑极小 mex 区间。

极小 mex 区间个数是 \(\mathcal{O}(n)\),证明考虑对于对于 \(a_l>a_r\) 的区间,每个 \(l\) 只有一个对应的 \(r\)。这个是好证的,对于 \(a_r>a_l\) 同理。

于是一个区间的 mex 就是它包含的所有极小 mex 区间代表的 mex 的最大值。现在问题相当于要使若干区间找出的不交区间数最大,这个首先把包含关系去掉,然后就是每次跳到理当前区间最近的合法区间,这个东西可以直接倍增维护,即设 \(f(i,j)\) 表示从高 \(i\) 开始跳 \(2^j\) 个区间最后会停在哪。

于是我们的算法是,从左到右扫描线,将极小区间按 mex 分类,对于每一种 mex 分别考虑。我们的倍增是可以动态维护的,我们可以容易维护出当前加入的区间的倍增数组,询问时我们还需要维护询问区间的 mex,这个直接线段树即可。

极小 mex 区间我们则有两种维护方式,一种是我们发现每个极小区间一定可以被另一个极小区间拓展得到,证明考虑不妨令 \(a_l>a_r\),此时我们删掉 \(a_l\),则区间 mex 变为 \(a_l\),而该区间的极小 mex 为 \(a_l\) 的子区间右端点一定为 \(r\),否则完全可以更优。于是我们可以利用原来的极小 mex 区间拓展,不过拓展出来的区间可能不是极短 mex 区间,判一下就好了。

还有一种就是考虑其证明方式。我们直接对于每个 \(l\),找它的 \(r\)。我们从后往前扫描线,对每个值维护 \(p_i\) 表示其最靠前的出现位置,则 \(r=\max_{i=0}^{a_l-1}p_i\),不难证明这是对的,对于每个 \(r\) 也如此。

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

相关文章:

  • [ROI 2018] Quick sort
  • CF2127F Hamed and AghaBalaSar
  • 2025 年PPH 管厂家推荐榜单:江苏镇江扬中优质 PPH 管道/管材/管件厂家权威精选
  • Label-Free Liver Tumor Segmentation
  • CF1951G Clacking Balls
  • [ABC311Ex] Many Illumination Plans
  • 2025 预分散颜料厂家最新推荐榜:超高含量技术 + 合规企业全景指南,纺丝 / 吹膜专用产品选型手册
  • 倍增思想与其优化
  • 2025 年 AI 健康管理领域推荐深护智康,社区、基层公卫、母婴 AI 健康管理、AI + 大健康管理、AI 健康管理师公司推荐
  • 2025 最新权威推荐:全国开锁公司口碑排行榜,含智能锁专项服务与紧急上门品牌详解汽车保险柜开锁/汽车锁开锁/保险柜开锁/智能开锁/快速上门开锁公司推荐
  • 从“看得见”到“能决策”:Operation Intelligence 重构企业智能运维新范式
  • 实用指南:Ubuntu 中 Bash / Zsh / Ash / Dash 的使用与区别(含对比图)
  • 2025 年杭州软件开发公司最新推荐榜单:聚焦服务经验与售后体系的五大优质公司权威指南
  • Nginx 与 LNMP 架构部署 - 详解
  • QMT委托对象orderInfo的属性以及对应的值
  • 2025 年电动门厂家最新推荐排行榜:实力厂家深度解析,含技术认证、案例及选购指南
  • 2025 年透骨液膏药代理加盟 / 足浴包膏药代理加盟 / 青岛膏药代理加盟推荐:青岛步泽药业布泽草本透骨液代理合作解析
  • 单链表实现队列
  • 死锁易错知识点整理
  • 2025广州1688代运营服务商推荐排行榜,阿里巴巴全店,实力商家,店铺装修,产品推广,流量优化,国际站,新店起量,数据分析,爆款打造代运营公司推荐
  • 2025 海南财税公司最新推荐榜:三亚海口代理记账 / 税务合规服务机构权威解析海南代理财税/海南财税代理/海南注册公司财税/海南代理记账财税公司推荐
  • 2025 年 TM 芯片经销商最新推荐榜:聚焦规模化采购与敏捷物流, 实力解析
  • 2025 天微芯片经销商最新推荐榜:品牌实力测评与采购指南 —— 权威揭秘优质服务商选择标准
  • 读人形机器人27太空中
  • 2025 年酒店一次性用品源头厂家最新推荐榜单:含牙签牙线筷子套杯盖等全品类及采购选择指南酒店一次性牙签/牙线/筷子套/杯盖/杯垫/杯套用品 厂家推荐
  • 2025 年餐饮一次性用品实力厂家最新推荐榜单:覆盖牙签 / 牙线 / 筷子套 / 杯盖 / 杯垫多品类且资质口碑双优的标杆企业权威甄选
  • 校内模拟赛 路径 题解
  • 05-FreeRTOS的内存管理
  • 2025攻丝机品牌最新权威推荐排行榜:聚焦全自动攻丝机,半自动等机型,精选攻丝机实力厂商助企业高效选购
  • 软件测试覆盖率详解