Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom12月前

07/12
20:20
二分法 树状数组

[bzoj 2738]矩阵乘法

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

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

♦♦♦♦♦♦   Input   ♦♦♦♦♦♦

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

♦♦♦♦♦♦   Output   ♦♦♦♦♦♦

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

♦♦♦♦♦♦   Sample Input   ♦♦♦♦♦♦

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

♦♦♦♦♦♦   Sample Output   ♦♦♦♦♦♦

1
3

♦♦♦♦♦♦   Hint   ♦♦♦♦♦♦

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

♦♦♦♦♦♦   题解  ♦♦♦♦♦♦

整体二分,每次把小于等于mid的数看作1插入到矩形中,用二维树状数组维护矩阵和,然后答案小于等于mid和大于mid的询问放到两边,分治就可以了

 

[bzoj 2738]矩阵乘法