记录编号	129639	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[HZOI 2014] 天使的小纸条	最终得分	100
用户昵称	ztx	是否通过	通过
代码语言	C++	运行时间	6.346 s
提交时间	2014-10-20 16:13:16	内存使用	15.61 MiB

/*
	author :hzoi_ztx
	title  :天使的小纸条 
	ALG    :树状数组+离线 
	comment:负数 = = 
			题目说c ≤100但不代表c > 0
			因此不同的颜色最多有 300*300+200000 =  290000
			假如开290000个树状数组 ・・・・・・
			当然，数据是比较弱的，最多有32755种颜色（因为直接输出的rand()）
			假如没看清题开100种颜色的树状数组，内存将是 300*300*100*4/1024/1024 = 32Mb 
			假如开32755种颜色，内存将是 300*300*32755*4/1024/1024 = 11246 Mb
			假如开290000种颜色的树状数组，不想算了 = = 
			就算给你 128Mb 也稳超内存 
			所以要用离线算法，将对同一种颜色的操作以链表的形式存起来后，再对每一种颜色进行操作 
			但是，将链表的端点存起来也不是一件容易事，所以可以借用一下STL的map映射
			如果有兴趣写平衡树什么的也是可以的 
			最终程序运行内存只有不到 16Mb 而已 
			
			PS：叫你们考试的时候不考虑负数 哼! 

     ."".    ."",
     |  |   /  /
     |  |  /  /
     |  | /  /
     |  |/  ;-._ 
     }  ` _/  / ;
     |  /` ) /  /
     | /  /_/\_/\
     |/  /      |
     (  ' \ '-  |
      \    `.  /
       |      |
       |      |
*/

#include <cstdio>
#include <cstring>
#include <map>

#define  maxn  301
#define  maxc  102
#define  maxq  200010
#define  maxt  490010

#define  lowbit(x)  x&(-x)

#define  Inst  1
#define  Qury  2

struct que{
	int mode , a , b , c , d , next , p ;
} q[maxt] ; int tot = 0 ;

int n , m ;
int C[maxn][maxn] = {0} ;
int data[maxn][maxn] = {0} ;
int ans[maxq] = {0} ;
int cnt = 0 ;
int rec[maxq] = {0} ;

std::map<int,int>Fstar ;
std::map<int,int>Bstar ;
std::map<int,bool>exist ;

void exchange(int&x , int&y) {
	if (x <= y) return ;
	int t = x ; x = y ; y = t ;
}

void add(int c,int p) {
	if (!Fstar[c]) {
		Fstar[c] = p ;
		Bstar[c] = p ;
	}
	else {
		q[Bstar[c]].next = p ;
		Bstar[c] = p ;
	}
}

void insert(int x , int y , int d) {
	for (int i = x ; i <= n ; i += lowbit(i) )
		for (int j = y ; j <= m ; j += lowbit(j) )
			C[i][j] += d ;
}

int query(int x , int y) {
	int ret = 0 ;
	for (int i = x ; i ; i -= lowbit(i) )
		for (int j = y ; j ; j -= lowbit(j) )
			ret += C[i][j] ;
	return ret ;
}

void solve(int v) {
	memset(C , 0 , sizeof(C)) ;
	int p = Fstar[v] , tmp;
	while (p) {
		if (q[p].mode == Inst) insert(q[p].a , q[p].b , q[p].c) ;
		else {
			tmp = query(q[p].a-1,q[p].c-1)+query(q[p].b,q[p].d)-query(q[p].b,q[p].c-1)-query(q[p].a-1,q[p].d) ;
			ans[q[p].p] = tmp ;
		}
		p = q[p].next ;
	}
}

int main() {
	#define READ
	#ifdef  READ
		freopen("luvletter.in" ,"r",stdin ) ;
		freopen("luvletter.out","w",stdout) ;
	#endif
	int i , j ;
	scanf("%d%d", &m , &n ) ;
	for (i = 1 ; i <= n ; i ++ ) {
		for (j = 1 ; j <= m ; j ++ ) {
			scanf("%d", &data[i][j] ) ;
			if (!exist[data[i][j]]) {
				rec[++rec[0]] = data[i][j] ;
				exist[data[i][j]] = true ;
			}
			tot ++ ; q[tot].mode = Inst ;
			q[tot].a = i ; q[tot].b = j ;
			q[tot].c = 1 ;
			add(data[i][j] , tot) ;
		}
	}
	int Q , mm , a , b , c , v ;
	scanf("%d", &Q ) ;
	while ( Q -- ) {
		scanf("%d", &mm ) ;
		if (mm == Inst) {
			scanf("%d%d%d", &a , &b , &c ) ;
			if (!exist[c]) {
				exist[c] = true ;
				rec[++rec[0]] = c ;
			}
			tot ++ ;
			q[tot].a = a ; q[tot].b = b ;
			q[tot].c = 1 ; q[tot].mode = Inst ;
			add(c , tot) ;
			tot ++ ;
			q[tot].a = a ; q[tot].b = b ;
			q[tot].c = -1 ; q[tot].mode = Inst ;
			add(data[a][b] , tot) ;
			data[a][b] = c ;
		}
		else {
			tot ++ ;
			q[tot].mode = Qury ;
			scanf("%d%d%d%d%d", &q[tot].a , &q[tot].b , &q[tot].c , &q[tot].d , &v ) ;
			exchange(q[tot].a , q[tot].b) ;
			exchange(q[tot].c , q[tot].d) ;
			q[tot].p = ++ cnt ;
			if (!exist[v]) {
				ans[cnt] = 0 ;
				tot -- ;
			}
			else add(v , tot) ;
		}
	}
	Bstar.clear() ;
	for (i = 1 ; i <= rec[0] ; i ++ ) {
		j = rec[i] ;
		solve(j) ;
	}
	for (i = 1 ; i <= cnt ; i ++ ) {
		printf("%d\n", ans[i] ) ;
	}
	#ifdef READ
		fclose(stdin ) ;
		fclose(stdout) ;
	#endif
	return 0 ;
}