P3522 [POI 2011] TEM-Temperature——单调队列之我的倍增怎么似了😭
我的倍增怎么似了😭
倍增解法(就要写)
考虑是否可以将两个区间并为一个等价的区间
将左端点变为左端点中最小值，右端点中最大值即可
当左侧的区间的左端点大于右侧区间的右端点时不能合并
于是可以将合并的过程倍增维护，枚举每个左端点，研究可以合并到的最右端区间
时间复杂度
空间一算，
单调队列
仔细想一下，如果只考虑从左到右合并，并完之后右端点在哪对于答案没有任何影响
也就是说，如果只考虑从左到右合并，只需要维护左端点即可，而加入的区间右端点决定它能合并哪些区间
又会发现，当右端点向右移动的时候，左端点是单调不降的
那么就可以考虑单调队列，队头放的是最左侧的区间，当要合并区间时先依照右端点把不能加入的区间去掉，再考虑并进一些区间
如果队尾出现了不单调递减的部分，那就可以用出队来维护，因为
- 当这个新加入的区间满足时，被出队的区间必定满足
- 当这个新加入的区间不满足时，被出队的区间就没办法接上了
于是就相当于合并成了一个等价的区间
然后可以在单调队列中维护每个区间的编号，然后就可以用编号来计算长度了
时间空间复杂度都是