画个图就明白了
by yinhee @ 2023-10-25 16:03:06
@[yinhee](/user/578590) emmm明白不了，这不是维护下凸包吗，斜率应该是递增的
那么这不就是普通单调队列维护递增的东西吗？那为什么是这样呢？
~~终于有人理我了~~感谢！
by Kniqht @ 2023-10-25 16:06:14
你单调队列不就是要弹出队尾大于要加入元素的元素吗？尾部小于它，那它直接加进去都是单调的啊
by yinhee @ 2023-10-25 16:12:27
@[yinhee](/user/578590) 不是，难道不是尾部大于他才是单调的吗？
维护的单调递增啊？
所以我们要弹出尾部小于等于它的啊？
谢谢您的解答！另外如果您回答了请@我谢谢不然可能看不到QAQ
by Kniqht @ 2023-10-25 16:20:07
@[Kniqht](/user/315205) 首先你是维护斜率单调递增的队列，然后你要加入一个元素在队尾，那么此时就要求队尾斜率要小于当前斜率。
by yinhee @ 2023-10-25 16:25:20
@[Kniqht](/user/315205)
出现这种情况时弹出 $Q_r$, 就是 $Q_r, i$ 之间的斜率小于 $Q_{r-1}, Q_r$ 之间的斜率
by sinsop90 @ 2023-10-25 16:27:12
@[sinsop90](/user/141599) @[yinhee](/user/578590) 艹，发现自己连单调队列都不会了。。不知道为什么把hh和tt想反了，也不知道上一个while怎么写出来的，十分感谢！
by Kniqht @ 2023-10-25 16:33:42
@[sinsop90](/user/141599) /bx/bx/bx
by yinhee @ 2023-10-25 16:34:59
@[sinsop90](/user/141599) @[yinhee](/user/578590) 但是感觉仍有一点疑问qwq，抱歉@了两遍，单调队列难道不是hh队头最大吗？那么为什么hh不在[sinsop90](/user/141599)大佬给的图的右边，而是tt在右边呢、
by Kniqht @ 2023-10-25 16:37:23
哦我说的hh就是代码中的l，单调队列的头
by Kniqht @ 2023-10-25 16:37:55