主题

主题

 
   

2738: 矩阵乘法

原题:http://www.lydsy.com/JudgeOnline/problem.php?id=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

  矩阵中数字是10^9以内的非负整数;

  20%的数据:N<=100,Q<=1000;

  40%的数据:N<=300,Q<=10000;

  60%的数据:N<=400,Q<=30000;

  100%的数据:N<=500,Q<=60000。


个人解法:

本来想做分块,但是看到题目以后怎么想就是想到了整体二分。

自然我们可以整体二分+二维树状数组。

时间复杂度O(nlog^3n)


代码如下:

https://code.csdn.net/snippets/2213874


本来自己YY想主席树的。但是确实YY不出怎么写二维主席树。不过自己瞎YY出了一个二维分块。

然后尝试写了一下。

 
 
评论