【BZOJ】1452: [JSOI2009]Count

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

}