cdq 分治的思路仍是处理跨过当前区间中点的贡献，但递归顺序是左子区间、当前区间、右子区间。这仍然满足处理当前区间时两个子区间的相对顺序不变（但左子区间不一定是有序的）
从嵌套数据结构的观点看，cdq 分治就是树套树外层树的中序遍历，优点是空间少一个 \(\log\) 且常数更小
LG4093 [HEOI2016/TJOI2016] 序列
记 \(mx[i],mn[i]\) 为位置 \(i\) 可能的最值
类似 LIS DP，转移条件是 \(i<j,mx[i]\le a[j],a[i]\le mn[j]\)
标签：左子,顺序,分治,cdq,当前,区间 From： https://www.cnblogs.com/ft61/p/17763096.html