zhr随机跳题跳到的，遂做之。注意到\(nk\le5\times10^5\)，考虑根号分治。当\(n\)很大时，\(k\)会很小，于是我们记录每一行的前缀和，每一次循环\(k\)个数组的前缀和取\(\max\)即可，时间复杂度\(O(qk)\)。当\(k\)很大时，\(n\)会很小，我们暴力预处理区间\([l,r]\)的最大值，

链接发现这东西就很根号分治。考虑两种情况：\(k\le1000\)，这部分直接用前缀和维护然后暴力做，时间复杂度\(O(kq)\)。\(k>1000\)，此时\(n\le500\)，这部分直接预处理答案，时间复杂度\(O(n^2k)\)。两个时间复杂度均正确，因此可以通过此题。代码：点击查看代码/*Tips