P1527 [国家集训队]矩阵乘法

\(\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}{输入样例}\)

\(\color{#0066ff}{输出样例}\)

1

3

\(\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<bits/stdc++.h>

#define LL long long

LL 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;

}

巴特西

P1527 [国家集训队]矩阵乘法

\(\color{#0066ff}{ 题目描述 }\)

\(\color{#0066ff}{输入格式}\)

\(\color{#0066ff}{输出格式}\)

\(\color{#0066ff}{输入样例}\)

\(\color{#0066ff}{输出样例}\)

\(\color{#0066ff}{数据范围与提示}\)

\(\color{#0066ff}{题解}\)

整体二分，显然一看n的范围，直接用二维树状数组来维护这个东西即可

最新文章

热门文章

巴特西

P1527 [国家集训队]矩阵乘法

\(\color{#0066ff}{ 题目描述 }\)

\(\color{#0066ff}{输入格式}\)

\(\color{#0066ff}{输出格式}\)

\(\color{#0066ff}{输入样例}\)

\(\color{#0066ff}{输出样例}\)

\(\color{#0066ff}{数据范围与提示}\)

\(\color{#0066ff}{题解}\)

整体二分， 显然一看n的范围，直接用二维树状数组来维护这个东西即可

最新文章

热门文章

整体二分，显然一看n的范围，直接用二维树状数组来维护这个东西即可