求问 #4 #5 是给什么做法留的

我知道 #1 是给 $O(qn^3)$ 留的，枚举区间有常数。

111111#2 #3 应该是给 $O(n^2q)$ 或者大常数 $O(n^2\log n+nq)$ 给的（#4 好像时空都卡了）。

111111#4 我猜是给小常数 $O(n^2\log n+nq)$，空间可过的，但是洛谷我卡了好半年才卡过不知道是错误硬过还是给他留的，根据计算一共 $1.4\times 10^9$，但是 2s，而且 CCF 机子快。

11111#5 不知道咋做，求做法。