概括
轻新小思路
用于处理点对关系题
在能将点对分段处理（如下）的题目中有奇效
试想，现在要处理部分点对，其范围为\(l\in [L,R],r\in [L,R]\)
其位置不确定，但是我们可以考虑将其分为三个板块分别作出的总贡献
即分为
\(l\in [L,mid],r\in[mid+1,R]\)
\(l\in [L,mid],r\in[L,mid]\)
\(l\in [mid+1,R],r\in[mid+1,R]\)
后面两者发现于一开始的大区间形式相同，可以递归处理，而第一类区间有着性质
即这些点是分开的，可以进行特殊处理
如三维偏序中，一开始可以排序确定一维的单调性，然后在处理这一类区间时，因为\([L,mid]\)中第一维一定大于\([mid+1,R]\)的第一维
所以可以将\([L,mid],[mid+1,R]\)中的数分别再通过第二维排序，这样就能在保证第一维的前提下，将第二，第三维同时也处理了
然后有例题Beautiful Pair
这题乍一看并没有什么像三维偏序一样明显的，可以通过分治为\([L,mid],[mid+1,R]\)的方式
However，可以进行深入思考
如很明显地，在处理特殊区间时可以处理出前/后缀最大值
没思路，先摸式子
看到\(a_i\cdot a_j\leq max\)可以换成\(a_i\leq \frac{max}{a_j}\)
可以考虑固定一边最大值，这样整个区间的最大值就能够被确定，因为处理了前/后缀最大值，所以上式可以替换为\(a_i\leq \frac{pre_j}{a_j}\)
这样就有一个显然的处理方式：可以设当最大值在左/右边时，对于其相反的一边，\(a_i\leq \frac{pre_j}{a_j}\)或\(a_j< \frac{suf_i}{a_i}\)的有多少
但是这样处理需要线段树或主席树（主席树处理更麻烦但是更方便），而数据范围是\(1e9\)
然后发现实际上需要记录的只有\(a_i\)和\(\frac{pre_i}{a_i}\)或\(\frac{suf_i}{a_i}\)
实际上只有\(2n\)种，可以离散化
由此可切
小结
学算法或DS后一定要先联系其他要用这种算法/DS的题目以构建知识体系
标签：frac,处理,99th,mid,2024,leq,CDQ,可以,最大值 From： https://www.cnblogs.com/tlz-place/p/18440822