题目名称	1780. [国家集训队2012]矩阵乘法
输入输出	`nt2012_mat.in/out`
难度等级	★★★☆
时间限制	2000 ms (2 s)
内存限制	256 MiB
测试数据	20
题目来源	cstdio 于2014-10-29加入
开放分组	全部用户
提交状态
分类标签	二分法分块树状数组整体分治
	分享题解

通过：59，提交：135，通过率：43.7%
天亮说晚安·	100	3.944 s	7.99 MiB	C++
AAAAAAAAAA	100	4.117 s	6.38 MiB	C++
Hzoi_Ivan	100	4.144 s	6.11 MiB	C++
zmy_wky	100	4.214 s	13.75 MiB	C++
Troywar	100	4.219 s	12.58 MiB	C++
HZOI_蒟蒻一只	100	4.710 s	6.27 MiB	C++
AntiLeaf	100	5.000 s	10.36 MiB	C++
HZOI_蒟蒻一只	100	5.045 s	5.79 MiB	C++
一個人的雨	100	5.590 s	5.95 MiB	C++
hzoi_xx	100	5.608 s	8.53 MiB	C++

关于矩阵乘法的近10条评论(全部评论)
分块大法好QAQ BaDBoY 2017-10-02 07:26 15楼
……智障如我，粘贴复制上面的add，忘了把加号改成减号…… `while(now<n*n&&a[now+1].val<=hashs[mid]){ ++now; add(a[now].x,a[now].y,1); } while(now&&a[now].val>hashs[mid]){ add(a[now].x,a[now].y,-1); now--; }` Troywar 2017-10-01 20:41 14楼
这个矩阵乘法。。。怎么乘来着？？ Regnig Etalsnart 2017-10-01 19:41 13楼
NOI，linux下编译运行正常输出答案。。。。。。cogs又挂了。。。再见 2017-05-12 20:23 12楼
1A感觉不错 ---------------- 吃完饭后评测机就是快啊两个代码一个T7.，一个T2 T7的重评A了 T2的重评A了评测机亮了 Go灬Fire 2017-02-14 07:04 11楼
整体二分大法好，二维bit报平安。 FoolMike 2017-01-04 20:04 10楼
窝要好好思考这个.... sxysxy 2016-12-10 17:37 9楼
树状数组套主席树炸内存了......orz...... AntiLeaf 2016-12-10 10:20 8楼
终于过了。。。虽然错了好多次。。。落尘 2015-07-10 15:19 7楼
我来学习一下分块的正确姿势…… Asm.Def 2015-06-27 00:05 6楼

1780. [国家集训队2012]矩阵乘法

★★★☆ 输入文件：nt2012_mat.in 输出文件：nt2012_mat.out 简单对比
时间限制：2 s 内存限制：256 MiB

矩阵乘法（梁盾）

时间限制：2.0s 内存限制：256.0MB

【问题描述】

给你一个N*N的矩阵，不用算矩阵乘法，但是每次询问一个子矩形的第K小数。

【输入格式】

第一行两个数N,Q，表示矩阵大小和询问组数；
接下来N行N列一共N*N个数，表示这个矩阵；
再接下来Q行每行5个数描述一个询问：x1,y1,x2,y2,k表示找到以(x1,y1)为左上角、以(x2,y2)为右下角的子矩形中的第K小数。

【输出格式】

对于每组询问输出第K小的数。

【样例输入】

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

【样例输出】

1
3

【数据规模和约定】

矩阵中数字是10⁹以内的非负整数；
20%的数据：N<=100,Q<=1000；
40%的数据：N<=300,Q<=10000；
60%的数据：N<=400,Q<=30000；
100%的数据：N<=500,Q<=60000。