雑用 4()

莫队的重学。

普通莫队的排序有很多讲究,以后只写回滚莫队好了,至少复杂度是稳定的。这是莫队的排序关键字:\((\textit{bel}_{ \text{left endpoint }}, \text{ right endpoint})\)。

回滚莫队和莫队还是有点区别的,具体而言就是对序列分块,块内询问暴力,跨块询问就根据左端点所在的块分类,将左端点在一个块内的询问拉出来,按照右端点排序,这样移动右端点就是单调的,而左端点每次从(所在)块的右端点 \(+1\) 的位置开始暴力跑,平衡了复杂度。

上面说的是只加不减莫队,只减不加莫队和这个有点区别。

首先还是按左端点所在块分类,然后右端点按降序排,莫队维护的区间右端点就从序列末端往前单调地跑就行了。只减不加莫队的区别在于,块内询问我们不必暴力了,直接跟着跑就行了。

举个例子,\(\texttt{[}\texttt{(}_1\texttt{)}_1\texttt{(}_2\texttt{)}_2\texttt{]}\)(方括号代表一个块,角标用以区分不同询问),如果是只加不减莫队的话,维护的右指针根本跑不到块内(从右端点开始单调向右跑),而只减不加莫队的右指针可以跑进来。注意两种莫队的左端点都是暴力的,所以不需要考虑。

高维莫队真的很没意思,就是强行加了一维时间轴,排序的关键字是 \((\textit{bel}_{\text{ left endpoint }}, \textit{bel}_{ \text{right endpoint }}, \text{ time stamp})\)。

如果有什么厉害的排序 trick 或其他 trick 或高庙题记得放上来。

————————

莫队的重学。

普通莫队的排序有很多讲究,以后只写回滚莫队好了,至少复杂度是稳定的。这是莫队的排序关键字:\((\textit{bel}_{ \text{left endpoint }}, \text{ right endpoint})\)。

回滚莫队和莫队还是有点区别的,具体而言就是对序列分块,块内询问暴力,跨块询问就根据左端点所在的块分类,将左端点在一个块内的询问拉出来,按照右端点排序,这样移动右端点就是单调的,而左端点每次从(所在)块的右端点 \(+1\) 的位置开始暴力跑,平衡了复杂度。

上面说的是只加不减莫队,只减不加莫队和这个有点区别。

首先还是按左端点所在块分类,然后右端点按降序排,莫队维护的区间右端点就从序列末端往前单调地跑就行了。只减不加莫队的区别在于,块内询问我们不必暴力了,直接跟着跑就行了。

举个例子,\(\texttt{[}\texttt{(}_1\texttt{)}_1\texttt{(}_2\texttt{)}_2\texttt{]}\)(方括号代表一个块,角标用以区分不同询问),如果是只加不减莫队的话,维护的右指针根本跑不到块内(从右端点开始单调向右跑),而只减不加莫队的右指针可以跑进来。注意两种莫队的左端点都是暴力的,所以不需要考虑。

高维莫队真的很没意思,就是强行加了一维时间轴,排序的关键字是 \((\textit{bel}_{\text{ left endpoint }}, \textit{bel}_{ \text{right endpoint }}, \text{ time stamp})\)。

如果有什么厉害的排序 trick 或其他 trick 或高庙题记得放上来。