\(\color{#0066ff}{ 题目描述 }\)
给你一个N*N的矩阵，不用算矩阵乘法，但是每次询问一个子矩形的第K小数。
\(\color{#0066ff}{输入格式}\)
第一行两个数N,Q，表示矩阵大小和询问组数；
接下来N行N列一共N*N个数，表示这个矩阵；
再接下来Q行每行5个数描述一个询问：x1,y1,x2,y2,k表示找到以(x1,y1)为左上角、以(x2,y2)为右下角的子矩形中的第K小数。
\(\color{#0066ff}{输出格式}\)
对于每组询问输出第K小的数。
\(\color{#0066ff}{输入样例}\)
2 22 13 41 2 1 2 11 1 2 2 3
\(\color{#0066ff}{输出样例}\)
13
\(\color{#0066ff}{数据范围与提示}\)
矩阵中数字是10^9以内的非负整数；
20%的数据：N<=100,Q<=1000；
40%的数据：N<=300,Q<=10000；
60%的数据：N<=400,Q<=30000；
100%的数据：N<=500,Q<=60000。
\(\color{#0066ff}{题解}\)
整体二分， 显然一看n的范围，直接用二维树状数组来维护这个东西即可
// luogu-judger-enable-o2#include#define LL long longLL in() { char ch; LL x = 0, f = 1; while(!isdigit(ch = getchar()))(ch == '-') && (f = -f); for(x = ch ^ 48; isdigit(ch = getchar()); x = (x << 1) + (x << 3) + (ch ^ 48)); return x * f;}const int maxn = 4e5 + 10;struct Tree {protected: int n; int st[555][555]; int low(int x) { return x & (-x); } int getans(int a, int b) { int re = 0; for(int i = a; i; i -= low(i)) for(int j = b; j; j -= low(j)) re += st[i][j]; return re; }public: void resize(int len) { n = len; } void add(int x, int y, int k) { for(int i = x; i <= n; i += low(i)) for(int j = y; j <= n; j += low(j)) st[i][j] += k; } int query(int a, int b, int x, int y) { return getans(x, y) - getans(x, b - 1) - getans(a - 1, y) + getans(a - 1, b - 1); }}s;struct node { int a, b, x, y, k, id; node(int a = 0, int b = 0, int x = 0, int y = 0, int k = 0, int id = 0): a(a), b(b), x(x), y(y), k(k), id(id) {}}q[maxn], ql[maxn], qr[maxn];int ans[maxn], n, m, num;void work(int l, int r, int nl, int nr) { if(l > r || nl > nr) return; if(l == r) { for(int i = nl; i <= nr; i++) if(q[i].id) ans[q[i].id] = l; return; } int mid = (l + r) >> 1, cntl = 0, cntr = 0; for(int i = nl; i <= nr; i++) { if(q[i].id) { int k = s.query(q[i].a, q[i].b, q[i].x, q[i].y); if(q[i].k <= k) ql[++cntl] = q[i]; else q[i].k -= k, qr[++cntr] = q[i]; } else { if(q[i].k <= mid) s.add(q[i].a, q[i].b, 1), ql[++cntl] = q[i]; else qr[++cntr] = q[i]; } } for(int i = nl; i <= nr; i++) if(!q[i].id && q[i].k <= mid) s.add(q[i].a, q[i].b, -1); for(int i = 1; i <= cntl; i++) q[nl + i - 1] = ql[i]; for(int i = 1; i <= cntr; i++) q[nl + cntl + i - 1] = qr[i]; work(l, mid, nl, nl + cntl - 1), work(mid + 1, r, nl + cntl, nr);}int main() { n = in(), m = in(); s.resize(n); for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) q[++num] = node(i, j, 0, 0, in(), 0); for(int i = 1; i <= m; i++) { num++; q[num].a = in(), q[num].b = in(); q[num].x = in(), q[num].y = in(); q[num].k = in(), q[num].id = i; } work(0, 1e9, 1, num); for(int i = 1; i <= m; i++) printf("%d\n", ans[i]); return 0;}