P3397 分块0pts wa
  • 板块P3397 地毯
  • 楼主lxy_qwq
  • 当前回复0
  • 已保存回复0
  • 发布时间2025/7/20 14:18
  • 上次更新2025/7/20 17:15:02
查看原帖
P3397 分块0pts wa
1050426
lxy_qwq楼主2025/7/20 14:18
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000 + 5;
const int MAXM = 40;
int a[MAXN][MAXN];
int lazy[MAXM][MAXN];
int n, m;
int pos[MAXN];//属于哪一个块
int L[MAXM], R[MAXN];
void query(int k, int l, int r) {
	int lx = pos[l], rx = pos[r];
	if (lx == rx) {
		for (int i = l; i <= r; i++) {
			a[k][i]++;
		}
	}
	else {
		for (int i = l; i <= R[lx]; i++) {
			a[k][i]++;
		}
		for (int i = pos[l] + 1; i < pos[r]; i++) {
			lazy[k][i]++;
		}
		for (int i = L[rx]; i <= r; i++) {
			a[k][i]++;
		}
	}
}
int main() {
	cin >> n >> m;
	int block = sqrt(n);
	int z = 1;
	for (int i = 1; i <= n; ) {
		int l = i;
		int r = min(i + block - 1, n);

		for (int j = l; j <= r; j++) {
			pos[j] = z;
		}

		i = r + 1;
		L[z] = l;
		R[z] = r;
		z++;

	}
	for (int i = 1; i <= m; i++) {
		int x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		for (int j = x1; j <= x2; j++) {
			query(j, y1, y2);
		}
	}

	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			cout << a[k][i] + lazy[k][pos[i]] << ' ';
		}
		cout << endl;
	}
	return 0;
}
2025/7/20 14:18
加载中...