Home
Problem
Status
Contest
Workbook
User
Group
Forum
Register
Login
{"managingGroups":{},"author":"hhc0716","updateTime":1701934801000,"title":"20231207 单调栈、单调队列总结","dislikeCnt":0,"content":"# 栈\n\n## 栈的高级理解:\n\n### 1. push pop getmin\n\n一道例题:\n\n一个数据结构,支持从尾部压入(弹出)元素和全局查询最小值。\n\n可以一个栈维护前两个操作,然后前缀最小值处理第三个操作。\n\n-----\n\n#### 1X. push pop pointset rangemin\n\n加入了单点修改,全局最小值变成区间最小值。\n\n跟 1. 相似,但是前缀最小值变成了扩展树状数组($O(\\log^2 N)$)。\n\n-----\n\n#### 1Z. push pop rangeset rangesum\n\n加入了区间修改,全局最小值变成区间和。\n\n一样是树状数组。\n\n-----\n\n#### 1XZ. push pop rangeset rangemin\n\n加入了区间修改,全局最小值变成区间最小值。\n\n理论上有可能能做,但不知道具体咋做。\n\n-----\n\n### 2. 前缀的后缀最大值\n\nCSP2023 PJ T2 就是一个鲜明的例子。\n\n-----\n\n## 题目\n\n### F LG-6510\n\n$N$ 头奶牛在熊大妈的带领下排成了一条直队。\n\n显然,不同的奶牛身高不一定相同……\n\n现在,奶牛们想知道,如果找出一些连续的奶牛,要求最左边的奶牛 $A$ 是最矮的,最右边的 $B$ 是最高的,且 $B$ 高于 $A$ 奶牛。中间如果存在奶牛,则身高不能和 $A,B$ 奶牛相同。问这样的奶牛最多会有多少头?\n\n从左到右给出奶牛的身高,请告诉它们符合条件的最多的奶牛数(答案可能是 $0,2$,但不会是 $1$)。\n\n### 思路\n\n首先对于每一个奶牛,我们求出这个奶牛作为右端点时最右边的一个不能当左端点的奶牛。\n\n在这个开区间里,能当左端点的奶牛必须是前缀的最右边的后缀最大值。\n\n一个静态,一个动态。\n\n时间 $O(N)$,空间 $O(N)$。\n\n-----\n\n### G LG-6503\n\n给出一个长度为 $N$ 的序列 $a_i$,求出下列式子的值:\n\n$$\n\\sum \\limits_{i \u003d 1}^N \\sum \\limits_{j \u003d 1}^N (\\max \\limits_{i \\le k \\le j} a_k - \\min \\limits_{i \\le k \\le j} a_k)\n$$\n\n### 思路\n\n先拆开来。以下只考虑 $\\sum \\limits_{i \u003d 1}^N \\sum \\limits_{j \u003d 1}^N (\\max \\limits_{i \\le k \\le j} a_k)$,因为这个下面的方法反过来即可求出 $\\sum \\limits_{i \u003d 1}^N \\sum \\limits_{j \u003d 1}^N (\\min \\limits_{i \\le k \\le j} a_k)$。\n\n考虑对于每一个 i 单独求解,可以发现每往左边遇到了一个比当前最大值还要大的元素就会更新最大值。\n\n那么就跟 F 一样的,前缀的最右边的后缀最大值,然后统计贡献即可。\n\n-----\n\n# 队列\n\n## 题目\n\n### N LG-1725\n\n在幻想乡,琪露诺是以笨蛋闻名的冰之妖精。\n\n某一天,琪露诺又在玩速冻青蛙,就是用冰把青蛙瞬间冻起来。但是这只青蛙比以往的要聪明许多,在琪露诺来之前就已经跑到了河的对岸。于是琪露诺决定到河岸去追青蛙。\n\n小河可以看作一列格子依次编号为 $0$ 到 $N$,琪露诺只能从编号小的格子移动到编号大的格子。而且琪露诺按照一种特殊的方式进行移动,当她在格子 $i$ 时,她只移动到区间 $\\lbrack i + L, i + R \\rbrack$ 中的任意一格。你问为什么她这么移动,这还不简单,因为她是笨蛋啊。\n\n每一个格子都有一个冰冻指数 $A_i$,编号为 $0$ 的格子冰冻指数为 $0$。当琪露诺停留在那一格时就可以得到那一格的冰冻指数 $A_i$。琪露诺希望能够在到达对岸时,获取最大的冰冻指数,这样她才能狠狠地教训那只青蛙。\n\n但是由于她实在是太笨了,所以她决定拜托你帮它决定怎样前进。\n\n开始时,琪露诺在编号 $0$ 的格子上,只要她下一步的位置编号大于 $N$ 就算到达对岸。","threadId":177733,"likeCnt":0,"createTime":1701927628000,"isWorkbook":false,"viewCnt":115,"openness":2,"fav":false,"id":4354,"trustable":false}