题目链接：
题目分析
题目名称 “矩阵乘法” 与题目内容没有任何关系..就像VFK的 A+B Problem 一样..
题目大意是给定一个矩阵，有许多询问，每次询问一个子矩阵中的第 k 小值。
我看了神犇的题解，使用一种非常神奇的做法：
将矩阵中的数排个序，从小到大填到矩阵中。每次填 Size 个（这里就是分块）。
然后每填完一次，就暴力重新求一下 Sum[][] （二维前缀和）, 然后枚举每个询问，看看这个询问的子矩形内已经填入的数是否不少于询问的 k 。
如果子矩形内已填入的数不少于询问的 k ，那么这个询问的答案一定就是在这一次填入的 Size 个数中，于是就枚举这 Size 个数，然后判断每个数是不是在子矩形内，就可以求出刚好填到第 k 个是哪个数了。
然后就可以将这次询问删掉了，用双向链表实现删除一个询问。
复杂度是 O(n^4 / Size + n^2 * q / Size + q * Size) ，然后用均值不等式求出一个最优的 Size 就可以了。
代码
#include#include #include #include #include #include using namespace std;typedef double LF;inline int gmin(int a, int b) {return a < b ? a : b;}const int MaxN = 500 + 5, MaxM = 60000 + 5;int n, m, Top, Blk, S, T;int Sum[MaxN][MaxN], Has[MaxN][MaxN];struct ENum{ int Num, x, y;} E[MaxN * MaxN];inline bool Cmp(ENum e1, ENum e2){ return e1.Num < e2.Num;}struct EQ{ int x, y, xx, yy, k, Ans, Prev, Next; bool Inside(ENum e) { return (e.x >= x && e.x <= xx) && (e.y >= y && e.y <= yy); }} Q[MaxM];inline int GetSum(int x, int y, int xx, int yy){ return Sum[xx][yy] - Sum[x - 1][yy] - Sum[xx][y - 1] + Sum[x - 1][y - 1];}int main(){ scanf("%d%d", &n, &m); Blk = (int)((LF)n * (1.0 + ((LF)n / sqrt((LF)m)))) + 1; Top = 0; for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) { scanf("%d", &E[++Top].Num); E[Top].x = i; E[Top].y = j; } sort(E + 1, E + Top + 1, Cmp); for (int i = 1; i <= m; ++i) scanf("%d%d%d%d%d", &Q[i].x, &Q[i].y, &Q[i].xx, &Q[i].yy, &Q[i].k); for (int i = 1; i < m; ++i) Q[i].Next = i + 1; for (int i = 2; i <= m; ++i) Q[i].Prev = i - 1; S = m + 1; T = m + 2; Q[S].Next = 1; Q[1].Prev = S; Q[m].Next = T; Q[T].Prev = m; int p; for (int i = 1; i <= Top; i += Blk) { p = gmin(i + Blk - 1, Top); for (int j = i; j <= p; ++j) Has[E[j].x][E[j].y] = 1; for (int j = 1; j <= n; ++j) for (int k = 1; k <= n; ++k) Sum[j][k] = Sum[j - 1][k] + Sum[j][k - 1] - Sum[j - 1][k - 1] + Has[j][k]; int j = Q[S].Next; while (j != T) { int CntNow = GetSum(Q[j].x, Q[j].y, Q[j].xx, Q[j].yy); if (CntNow >= Q[j].k) { int Pos = p; while (CntNow >= Q[j].k) { if (Q[j].Inside(E[Pos])) --CntNow; --Pos; } Q[j].Ans = E[Pos + 1].Num; Q[Q[j].Next].Prev = Q[j].Prev; Q[Q[j].Prev].Next = Q[j].Next; } j = Q[j].Next; } } for (int i = 1; i <= m; ++i) printf("%d\n", Q[i].Ans); return 0;}