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

P12704 Retribution

我也不知道为什么能过做法。

考虑暴力缩点,然后做线段树合并。

细节上,由于要在可持久化线段树上合并,所以每次要新开节点,在合并的时候多剪枝减少栈调用和新开节点。
如果尝试将询问离线挂在每个 SCC 上的话,\(10^6\) 的无序 vector 应该还不如存新节点。

如果乱开东西大概率空间会炸。
一共有 \(10^6\) 个 SCC,注意到线段树上实际有非常多节点都连向同一个节点每次新建的点并不会很多。
实际精细计算一下空间只要 \(9\times 10^7\) 个 int 就行。千万不要乱开 vector。

留下不到一百兆给栈调用和临时的队列啥的应该是差不多够了,事实上对于数据是刚刚好。

代码。

后话

机房里大家都觉得这种东西非常假(我也觉得很假,但是就是写了然后过了),但实测这玩意跑得飞快。

我们在做合并的时候,只要发现处于同一个点就可以直接退出。而题里给出的图,会使得有非常多的线段树共用了同一个节点,合并复杂度事实上非常跑不满。

根据我本人精心构造的数据以及对数据点的判断,线段树新开的节点实际非常少大概在 \(O(n^2\log{n^2})\),合并次数大概在 \(O(n\log^2n)\) 级别。这是绰绰有余的。

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

相关文章:

  • Sunny Pro 网络验证- 仅需一键,即可为您的exe添加高强度防破加密!
  • 一条mysql数据库更新语句
  • 浅谈递归入门(1) - 指南
  • python+uniapp基于微信小工具的医院陪诊预约系统
  • [深度学习] 大模型学习5-高效微调框架Unsloth使用指北
  • 【APK安全】组件安全核心风险与防御指南 - 详解
  • 前端-JavaScript简介JavaScript模块化 - 努力-
  • 基本地址变换机构
  • 2025工业网线厂家权威推荐榜:千兆/拖链/高柔/网线/六类/超五类/6类/超5类/千兆/超六类/8芯/4芯/成品/相机/视觉数据工业网线高强屏蔽与稳定传输实力之选
  • gitee 使用安装教程
  • VisualMimic——基于视觉的人形行走-操作控制:低层策略负责平衡控制且跟踪高层下发的指令、高层策略则基于自我中心视觉输入生成任务跟踪指令 - 实践
  • 基本分页存储管理的基本概念
  • luogu P6503 [COCI 2010/2011 #3] DIFERENCIJA
  • 详细介绍:自动化接口框架搭建分享-pytest第三部分
  • Solon Plugin 自动装配机制详解
  • 2025宅基地纠纷律所权威推荐榜:专业调解与胜诉保障实力之选
  • 2025上海骨灰盒哪里买优质厂家权威推荐榜:匠心工艺与品质服务之选
  • 实用指南:华为 HCIA-Datacom 备考:VRP 通用路由平台原理-实操
  • Voice Agent Camp 结营!完整项目名单公布丨超音速计划 2025
  • 2025上海寿衣哪里买权威推荐:优质供货商与暖心服务之选
  • AI 真能胜任专业工程师的工作吗?
  • 容器中与内存相关的几个参数
  • 第一次软工作业
  • OpenWRT中备份多个docker容器的脚本 -
  • 动态分区分配算法
  • 上海殡葬一条龙服务权威推荐:寿衣、骨灰盒购买定制服务暖心陪伴与专业仪式之选
  • potplayer截图
  • OpenAI发布提示词集
  • 303、杂诗
  • 完整教程:第三方软件测试公司:【Gatling基于Scala的开源高性能负载测试工具】