P1527 [国家集训队] 矩阵乘法

问题：$n\times n$ 矩阵上的区间第 $k$ 大。$1\le n\le500$，$1\le m\le60000$。

整体二分板子题对我这个树套树爱好者来说就是树套树进阶题。所以考虑线段树套主席树，内层记录每一行的值域，支持 $O(\log n)$ 查询。外层是记录区间，把矩阵询问转化为 $O(\log n)$ 个区间询问。最外层二分答案。时间复杂度 $T(插入复杂度+查询数\times查询复杂度\times二分复杂度)=T(n^2\log^2n+m\log^2n\log n^2)=T(n^2\log^2n+2m\log^3n)$，算下来大概是 $25,000,000+120,000,000=145,000,000=1.45\times10^8=O(勉强能过)$。但是空间复杂度 $T(插入个数\times被插入的区间个数\times主席树插入所需空间\times大约的空间常数)=T(n^2\times2\log n\times\log n\times 3)=T(6n^2\log^2n)$。以上计算采用的是每棵主席树里面都各自离散化，算下来也是 $\ge140MB$ 爆炸。

经分析发现问题主要出在外层树开了太多主席树，所以考虑减少主席树的数量。把外层树换成分块，空间复杂度 $T((零散块空间+整块空间)\times大约的空间常数)=T((n^2\log n+\sqrt n\times n\sqrt n\log n\sqrt n)\times3)=T(3n^2\log n^\frac{5}{2})$，算下来大概是 $64MB$ 很稳。但是时间变成了 $T(m\times(\sqrt n\log n\sqrt n+\sqrt n\log n))=T(m\sqrt n\log n^\frac{5}{2})$，算下来是 $3\times10^8=O(非常悬)$，虽然时限是 $1.5s$，但是分块的常数也不小，所以说还是很困难。

所以我想问一下：有没有人有方法以空间换时间的？或者说有没有其他的树套树解法？

我不期望得到靠谱的答案，所以不太靠谱的也可以。