Louis_lxy @ 2024-08-26 21:57:45
如题，这种神奇的做法思路是用单调栈维护右边第一个不小于它的或者不大于它的（取决于最小还是最大），然后暴力模拟，如果上一个数刚好是最大值，那么就更新最大值，暴力往后面扫，然后用类似并查集的方法路径压缩。就 AC 了，记录如下：https://www.luogu.com.cn/record/174884841
求证明此做法时间复杂度正确或者提供 hack 的方法。
by Disjoint_cat @ 2024-08-26 22:11:53
@Louis_lxy 你除了单调栈剩下的都是一层循环你咋 T。
by Louis_lxy @ 2024-08-26 22:16:25
@Disjoint_cat 额，find的时间呢，虽然我也觉得不会 T 掉。
by Louis_lxy @ 2024-08-26 22:22:11
我感觉至少要证明一下这个均摊是
by Disjoint_cat @ 2024-08-26 22:29:10
@Louis_lxy 《你路径压缩了复杂度还能不对？？》
by Louis_lxy @ 2024-08-26 22:30:18
emmm，好吧