首页 > 其他分享 >丹钓战

丹钓战

时间:2024-08-08 11:28:24浏览次数:6  
标签:弹出 top 元素 栈顶 leq nul 丹钓战

其实就是简记一下单调栈的一个很好的理解方式,来源 writings.sh。

以单调递减的单调栈为例。因为如果要加入元素肯定都要先依次弹出栈顶,使加入新元素后能满足单调性。这里就是弹出不比新元素大的栈顶。假设目前准备加入一个新元素 \(x\),正在弹栈(栈顶是需要被弹出的,\(s_{top}\)),栈底是 \(s_0\)。那么,有如下的性质:

  1. \(s_{top} \leq x\)。按弹出的定义就有了。
  2. \(s_0\) 一定是目前扫到的最大值。因为如果有不比它小的一定会使它被弹出。
  3. \(s_{top}\) 在原数组中下一个不比它小的元素为 \(x\)。因为如果中间存在一个不比它小的元素,一定会在 \(x\) 之前使它被弹出。这个可以解决 NGE(Next Greater Element)问题。
  4. 假设 \(x\) 已经弹出了一些栈中元素,那么由 1 有 \(s_{top} \leq x\),又因为栈是单减的,有 \(lst < s_{top}\)。这就是 “\(x\) 的局部长板效应”:\(lst < s_{top} \leq x\)。
  5. \(s_{top}\) 是在栈内上一个元素 \(s_{top - 1}\) 和 \(x\) 之间(不含端点)的最大元素。首先由 3 可以得到一部分,而如果在 \(s_{top - 1}\) 到 \(s_{top}\) 之间存在比 \(s_{top}\) 更大的元素 \(nul\),假设 \(nul\) \(\geq s_{top - 1}\),\(s_{top - 1}\) 就会被弹出,矛盾;而如果 \(s_{top - 1} > nul > s_{top}\),它就会存在于 \(s_{top - 1}\) 和 \(s_{top}\) 之间,矛盾。这就是 “\(s_{top}\) 的局部长板效应”。和悬线法有点关系,也可能用于更新贡献(\(s_{top - 1} + 1\) 到 \(s_{top}\) 的位置,见 Pudding Monsters)。

标签:弹出,top,元素,栈顶,leq,nul,丹钓战
From: https://www.cnblogs.com/liuzimingc/p/18348606/stack

相关文章

  • P8251 [NOI Online 2022 提高组] 丹钓战 题解
    本文写于2022-03-2614:45:14。原博客地址题目链接算法(倍增)$O((n+q)\logn)$为简便,把元素$(a_i,b_i)$称为元素$i$。对一个区间$[l,r]$模拟一遍,从空栈开始,头......
  • [luogu p8251] [NOI Online 2022 提高组] 丹钓战
    [P8251NOIOnline2022提高组]丹钓战-洛谷|计算机科学教育新生态(luogu.com.cn)容易发现对于一次查询\([L,R]\),\(L\)一定是第一个入栈的,也是成功的,答案至少为......