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

浅谈 Bakas Trick / 不带删尺取 / 对顶栈

1. 算法介绍

1.1 普通队列

问题:维护一个队列,支持 pop_frontpush_back,查询队列内所有元素的信息和。保证该信息具有结合律。不保证该信息具有可差分性。

平凡的做法是用线段树或 ST 表维护这种不可差分的信息,然后跑双指针,时间复杂度大部分情况下会比普通双指针多一个 \(\log\)

Baka's Trick / 不带删尺取 / 对顶栈 则通过记录前后缀信息,结合均摊复杂度,在大多数情况下可以将时间复杂度减少一个 \(\log\)

具体而言,算法本质上是维护了一个对顶栈,来模拟队列的操作:

  • 假设有两个栈:\(stk1, stk2\)\(stk1\) 存出队的元素信息,\(stk2\) 存入队的元素信息。
  • 入队时,直接扔到 \(stk2\) 栈顶,并且记录 \(stk2\) 栈内的前缀信息,以方便撤销入栈。
  • 出队时:
    • \(stk1\) 内仍有元素,则直接出队,回退版本。
    • 否则说明 \(stk1\) 内没有元素,将 \(stk2\) 内的元素全部堆进 \(stk1\)
  • 查询时,直接将两个栈的前缀信息合并即可。

因为每个元素最多只会进入一次 \(stk1\),因此时间复杂度 \(O(nB)\)。其中 \(B\) 指将两个信息合并的复杂度。

三指针的写法和对顶栈本质是一样的,个人感觉对顶栈更直观。

1.2 双端队列

问题:维护一个双端队列,支持 pop_frontpop_backpush_frontpush_back,查询队列内所有元素的信息和。保证该信息具有结合律。不保证该信息具有可差分性。

和维护普通队列差不多,但是运用了一些均摊技巧。

发现难点在于删除元素的时候要把两个栈里的元素倒过来又倒回去,时间复杂度可能会爆炸。这里有一种暴力重构的方法可以解决这个问题:每次遇到删除的栈为空的时候,暴力重构另一个栈,使得当前的两个栈大小之差不超过 \(1\)

时间复杂度依然是 \(O(nB)\) 的。证明可以考虑势能分析,假设 \(\omega\) 表示当前两个栈大小的绝对值之差,则每次 push 操作最多会使得势能增加 \(1\);而每次删除操作要么使得势能增加 \(1\),要么将势能降到小于等于 \(1\)。而总共只能增加 \(q\) 的势能,所以时间复杂度依然是 \(O(nB)\) 的。

2 例题

2.1 CF1548B Integers Have Friends

2.2 LOJ P6515 「雅礼集训 2018 Day10」贪玩蓝月

2.3 AT_jag2018summer_day2_d Knapsack And Queries

2.5 UOJ P693 【UR #23】地铁规划

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

相关文章:

  • 聚变堆:中国BEST装置全面开建
  • web
  • 如何用pivotby函数实现数据透视(2)
  • 2025 年彩钢板厂家 TOP 企业品牌推荐排行榜,复合彩钢板,保温彩钢板,耐腐蚀彩钢板,净化彩钢板推荐这十家公司!
  • 251002
  • AT_agc020_d [AGC020D] Min Max Repetition
  • 题解:P7810 [JRKSJ R2] Upper
  • 记录自己被AWS坑了6刀
  • 如何用pivotby函数实现数据透视(1)
  • 10/1
  • 详细介绍:【数据结构】图论核心应用:关键路径算法详解——从AOE网到项目管理实战​
  • tnkstat3e-merge-0
  • JavaScript零基础入门速通(完整) - 指南
  • @RequestParam 什么时候可以省略?
  • 段页式管理方式
  • 推进电子设计革新:为什么模拟仿真正是核心助力?
  • 深入解析:前端开发,iframe 相关经验总结
  • list 容器 listr容器与vector容器 list 示例代码
  • advance 函数
  • *和 指针与地址 ++i和 i++
  • Playwright MCP浏览器自动化详解指南 - 教程
  • 指针和地址的示例运用代码
  • Python获取视频文件的各种属性信息
  • Arduino-Yun-物联网指南-全-
  • 2025雕塑厂家TOP企业品牌推荐排行榜,婚庆泡沫雕塑,玻璃钢,城市地标不锈钢,校园筑铜,道具,文旅,婚礼堂泡沫,直播间实景泡沫,水泥景观,商业美陈发光雕塑公司推荐!
  • Code--Blocks-和-C---应用开发-全-
  • 深入解析:(27)APS.NET Core8.0 堆栈原理通俗理解
  • VMware Service某些服务关闭导致虚拟机开机无法获取IP地址
  • 2025中国无缝钢管厂家 TOP 品牌权威推荐,SA106 无缝钢管,A106B 无缝钢管,SA53B 无缝钢管精选无缝钢管工厂
  • 在AI技术唾手可得的时代,挖掘用户真实需求成为产品成功的关键——某知名设备电量监控工具需求探索