1753. [HZOI 2014] 天使的小纸条

题目

天使的小纸条（luvletter）

背景

“我们都是小怪兽，总有一天会被正义的奥特曼消灭。”

——上杉绘梨衣

题目描述

某夜,天使大人在看《龙族》时，窗外传来一阵幽香，让熬夜看书的天使大人昏昏欲睡。不久，便进入了梦乡。

梦中，天使大人变成了废柴路鸣非，而时间恰好在路鸣非“拐走”绘梨衣时开始流动，一切都像小说中那么顺利，每天仍就只是两双眼睛的对视和传来传去的小纸条，还有在酒德麻衣精心编织的爱情剧本中毫无察觉。

只是，绘梨衣每天缠着天使大人玩游戏。怎奈何,他每次都被绘梨衣虐的很惨。这让我们的小公主很生气,认为天使大人心不在焉。于是，在小纸条上下了最后通牒，如果天使大人再不认真陪她玩，她就要离开。最后，她给了天使大人写着规则的小纸条，便不再理他。

这让我们的天使大人很头痛，因为他知道旁边这个小公主的力量，可以在30分钟内毁灭整个东京城。而且，作为一个男人(尽管是废柴),也不能被一个女生瞧不起，于是，他去求助路子航和凯撒，可作为整个牛郎店的红人，他们实在脱不开身。小魔鬼路明泽还在度假，于是他只能求助作为Oier的你。

绘梨衣的纸条上写着一个简单的游戏：数颜色…

乍一看，好像很简单，可是接下来的操作让天使大人眼花缭乱。唉，S级的血统还是比不上白王血裔的皇。天使大人叹了口气，无奈的摇了摇头…剩下的就交给你了。

纸条的一边写着一个N*M 的矩阵，每个位置都有一种颜色，绘梨衣可以对该矩阵不断进行操作，有时会改变某一位置的颜色，还不时让天使大人计算出一个矩形内特定颜色的个数。

这次绘梨衣很生气，为了知道天使大人是不是真的很认真的在玩。所以，她做了很多次操作，使整个游戏变得异常复杂，但是，这次天使大人已经毫无退路，所以你一定要算出来！！

输入数据

第一行有两个数字M,N

接下来N 行，每行M 个数，第i+1 行第j 个数表示格子（i，j）的初始值。

接下来一个整数Q

接下来Q 行，每行描述一个操作

操作1：“1 X Y C”(不含引号),表示将格子(X,Y)的权值改为C

操作2：“2 X1 X2 Y1 Y2 C”(不含引号)，表示询问矩形内有多少个位置的权值为C。X1,X2 分别为矩形中的两个横坐标，Y1,Y2 为矩形中的两个纵坐标。

输出数据

对于每一个操作2，输出一个整数表示答案，每数一行。

输入样例

3 3

1 2 3

3 2 1

2 1 3

3

2 1 2 1 2 1

1 2 3 2

2 2 3 2 3 2

输出样例

1

2

数据范围

对于30%的数据：1<=N,M<=30,Q<=50000

对于100%的数据：1<=N,M<=300,Q<=200000,C<=100,

对于所有操作1：1<=X<=N,1<=Y<=M

对于所有操作2：1<=X1<=X2<=N,1<=Y1<=Y2<=M.

来源

Hzoi2014