【BZOJ】1452: [JSOI2009]Count

浏览数：44 / 时间：2015年06月09日

http://www.lydsy.com/JudgeOnline/problem.php?id=1452

题意：n×m的矩阵上每个点有个颜色，现在有q个操作：1 x y c 将点(x,y)的颜色改为c；2 x1 x2 y1 y2 c 询问矩阵x1y1-x2y2颜色为c的格子数目

#include <bits/stdc++.h>
using namespace std;

const int N=301;
int n, m;
int S[101][N][N], col[N][N];
void upd1(int c[N], int x, int w) { for(; x<=m; x+=x&-x) c[x]+=w; }
void upd2(int c[N][N], int x, int y, int w) { for(; x<=n; x+=x&-x) upd1(c[x], y, w); }
int sum1(int c[N], int x) { int ret=0; for(; x; x-=x&-x) ret+=c[x]; return ret; }
int sum2(int c[N][N], int x, int y) { int ret=0; for(; x; x-=x&-x) ret+=sum1(c[x], y); return ret; }
void upd(int c[N][N], int x, int y, int s) {
	upd2(c, x, y, s);
}
int sum(int c[N][N], int xa, int ya, int xb, int yb) {
	int ret=0;
	ret+=sum2(c, xb, yb); // cout << " ret: " << ret << endl;
	ret-=sum2(c, xb, ya-1);
	ret-=sum2(c, xa-1, yb);
	ret+=sum2(c, xa-1, ya-1);
	return ret;
}

int main() {
	scanf("%d %d", &n, &m);
	for(int i=1; i<=n; ++i) for(int j=1; j<=m; ++j) {
		int x; scanf("%d", &x);
		col[i][j]=x;
		upd(S[x], i, j, 1);
	}
	int q;
	scanf("%d", &q);
	for(int cc=0; cc<q; ++cc) {
		int ch;
		scanf("%d", &ch);
		if(ch==1) {
			int x, y, cl;
			scanf("%d %d %d", &x, &y, &cl);
			upd(S[col[x][y]], x, y, -1);
			col[x][y]=cl; 
			upd(S[col[x][y]], x, y, 1);
		}
		else {
			int xa, xb, ya, yb, w;
			scanf("%d%d%d%d%d", &xa, &xb, &ya, &yb, &w);
			printf("%d\n", sum(S[w], xa, ya, xb, yb));
		}
	}
	return 0;
}

二维bit......

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

【BZOJ】1452: [JSOI2009]Count