题意
给定一个矩阵，每次询问子矩阵的第 \(k\) 大。
Sol
考虑把莫队扔到二维上来做。
发现复杂度变为：\(O(n ^ 2 q ^ {\frac {3}{4}})\)。
卡卡常就过了。
Code
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <array>
#include <cmath>
#include <vector>
#include <cassert>
#define il inline
#define rg register
using namespace std;
#ifdef ONLINE_JUDGE
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
char buf[1 << 23], *p1 = buf, *p2 = buf, ubuf[1 << 23], *u = ubuf;
#endif
int read() {
int p = 0, flg = 1;
char c = getchar();
while (c < '0' || c > '9') {
if (c == '-') flg = -1;
c = getchar();
}
while (c >= '0' && c <= '9') {
p = p * 10 + c - '0';
c = getchar();
}
return p * flg;
}
void write(int x) {
if (x < 0) {
x = -x;
putchar('-');
}
if (x > 9) {
write(x / 10);
}
putchar(x % 10 + '0');
}
const int N = 505, M = 2.5e5 + 5;
array <array <int, N>, N> mp;
namespace Cpt {
short bsi = 11;
array <short, M> agc;
class Node {
public:
short l1, r1, l2, r2;
int k, id;
Node () : l1(), r1(), l2(), r2(), k(), id() {}
Node (short _l1, short _l2, short _r1, short _r2, int _k, int _id) {
l1 = _l1, r1 = _r1, l2 = _l2, r2 = _r2, k = _k, id = _id;
}
il bool operator <(const Node &t) const {
if (agc[l1] != agc[t.l1]) return l1 < t.l1;
if (agc[l2] != agc[t.l2]) return (agc[l1]) & 1 ? l2 < t.l2 : l2 > t.l2;
if (agc[r2] != agc[t.r2]) return (agc[l2]) & 1 ? r2 < t.r2 : r2 > t.r2;
else return (agc[r2]) & 1 ? r1 < t.r1 : r1 > t.r1;
// if (l1 / bsi != t.l1 / bsi) return l1 < t.l1;
// if (r1 / bsi != t.r1 / bsi) return (l1 / bsi) & 1 ? r1 < t.r1 : r1 > t.r1;
// if (r2 / bsi != t.r2 / bsi) return (r1 / bsi) & 1 ? r2 < t.r2 : r2 > t.r2;
// else return (r2 / bsi) & 1 ? l2 < t.l2 : l2 > t.l2;
}
};
array <Node, M> edge;
namespace Blk {
short bsi = 610;
array <int, M> cur;
array <int, N> bk;
array <int, M> arc;
il int calc(int x) {
return (x - 1) / bsi + 1;
}
il void modify(int x, short y) { cur[x] += y, bk[arc[x]] += y; }
il int query(int k) {
rg short tot = 0;
for (rg short i = 1; i <= 500; i++) {
if (k - bk[i] <= 0) {
tot = i;
break;
}
k -= bk[i];
}
rg int ans = 0;
for (rg int i = (tot - 1) * bsi + 1; i <= min(tot * bsi, (int)2.5e5); i++) {
k -= (int)cur[i];
if (k <= 0) {
ans = i;
break;
}
}
// assert(ans >= 0);
return ans;
}
}
il void modify(short x1, short x2, short y1, short y2, short k) {
for (rg short i = x1; i <= x2; i++)
for (rg short j = y1; j <= y2; j++)
Blk::modify(mp[i][j], k);
}
}
vector <int> isl;
array <int, M> ans;
int main() {
rg int n = read(), m = read();
Cpt::bsi = n / pow(m, 0.25) / 3 + 1;
Cpt::Blk::bsi = n + 1;
for (short i = 1; i <= n; i++) Cpt::agc[i] = (i - 1) / Cpt::bsi + 1;
for (int i = 1; i <= n * n; i++) Cpt::Blk::arc[i] = (i - 1) / Cpt::Blk::bsi + 1;
for (rg short i = 1; i <= n; i++)
for (rg short j = 1; j <= n; j++)
mp[i][j] = read(), isl.push_back(mp[i][j]);
sort(isl.begin(), isl.end());
isl.erase(unique(isl.begin(), isl.end()), isl.end());
for (rg short i = 1; i <= n; i++)
for (rg short j = 1; j <= n; j++)
mp[i][j] = lower_bound(isl.begin(), isl.end(), mp[i][j]) - isl.begin() + 1;
// for (int i = 1; i <= n; i++) {
// for (int j = 1; j <= n; j++)
// write(mp[i][j]), putchar(32);
// puts("");
// }
for (rg int i = 1; i <= m; i++) {
rg short x1 = read(), y1 = read(), x2 = read(), y2 = read();
rg int k = read();
Cpt::edge[i] = Cpt::Node(x1, y1, x2, y2, k, i);
}
sort(Cpt::edge.begin() + 1, Cpt::edge.begin() + 1 + m);
rg short l1 = 1, l2 = 1, r1 = 1, r2 = 1; Cpt::Blk::cur[mp[1][1]]++, Cpt::Blk::bk[Cpt::Blk::calc(mp[1][1])]++;
for (int i = 1; i <= m; i++) {
rg short x1 = Cpt::edge[i].l1, x2 = Cpt::edge[i].l2,
y1 = Cpt::edge[i].r1, y2 = Cpt::edge[i].r2;
// write(x1), putchar(32);
// write(y1), puts("@");
while (l1 > x1) l1--, Cpt::modify(l1, l1, l2, r2, 1);
while (l2 > x2) l2--, Cpt::modify(l1, r1, l2, l2, 1);
while (r1 < y1) r1++, Cpt::modify(r1, r1, l2, r2, 1);
while (r2 < y2) r2++, Cpt::modify(l1, r1, r2, r2, 1);
while (l1 < x1) Cpt::modify(l1, l1, l2, r2, -1), l1++;
while (l2 < x2) Cpt::modify(l1, r1, l2, l2, -1), l2++;
while (r1 > y1) Cpt::modify(r1, r1, l2, r2, -1), r1--;
while (r2 > y2) Cpt::modify(l1, r1, r2, r2, -1), r2--;
ans[Cpt::edge[i].id] = Cpt::Blk::query(Cpt::edge[i].k);
}
for (rg int i = 1; i <= m; i++) {
// assert(ans[i] > -2);
write(isl[ans[i] - 1]), puts("");
}
return 0;
}