OI Problems   关于

#ox8kfm. 矩阵乘法

时间限制:1.5 s       空间限制:125 MiB       标签: 整体二分 数据结构 树状数组 二维树状数组 扫描线 离散化 莫队 二维莫队 

算法难度等级:6       思维难度等级:4       实现难度等级:5


本题来源于:国家集训队

题目描述

给你一个 n×nn \times n 的矩阵,不用算矩阵乘法,但是每次询问一个子矩形的第 kk 小数。

输入格式

第一行有两个整数,分别表示矩阵大小 nn 和询问组数 qq

22 到第 (n+1)(n + 1) 行,每行 nn 个整数,表示这个矩阵。第 (i+1)(i + 1) 行的第 jj 个数表示矩阵第 ii 行第 jj 列的数 ai,ja_{i, j}

接下来 qq 行,每行五个整数 x1,y1,x2,y2,kx_1, y_1, x_2, y_2, k,表示一组询问,要求找到以 (x1,y1)(x_1, y_1) 为左上角,(x2,y2)(x_2, y_2) 为右下角的子矩形中的第 kk 小数。

输出格式

对于每组询问,输出一行一个整数表示答案。

样例输入输出

2 2
2 1
3 4
1 2 1 2 1
1 1 2 2 3
1
3

数据范围

  • 对于 20%20\% 的数据,保证 n100n \leq 100q103q \leq 10^3
  • 对于 40%40\% 的数据,保证 n300n \leq 300q104q \leq 10^4
  • 对于 60%60\% 的数据,保证 n400n \leq 400q3×104q \leq 3 \times 10^4
  • 对于 100%100\% 的数据,保证 1n5001 \leq n \leq 5001q6×1041 \leq q \leq 6 \times 10^40ai,j1090 \leq a_{i, j} \leq 10^9