P10743: 情书密码
传统题
1.000s
时间限制
128MB
内存限制
4 提交
2 解决
【题目描述】
有消息称：绝恋找到了自己的Miss Right，正准备自己的表白。绝恋已经写好了情书，但为了避免其它人截获，他对情书进行加密。
为了打探绝恋的私密，你冒着生命危险终于搞到了这封情书。原以为可以轻易将情书解密，结果竟然发现聪明的绝恋并没有直接写出加密用的密码，而是在那粉红色的信纸背面写着“T=你的幸运数字”。
就这么放弃了吗？不，作为一个高智商的OIer，你决不轻言放弃。你还搞到了绝恋做密码时的草稿，通过一定的分析，你发现草稿中隐藏了绝恋的密码，具体规则如下：
草稿纸上写着一个N*M 的矩阵，每个位置都有一个数字C，绝恋对该矩阵不断进行操作，有时会修改某一位置的值，还不时计算出一个矩形内特定数字的个数作为密码的一部分，绝恋十分聪明，他进行了许多次这样的操作，因此密码也异常复杂，但是你已经下定决心要算出密码了，所以你一定要算出来！！
【输入】
第一行有两个数字N,M
接下来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 为矩形纵坐标中的最小值和最大值。
【数据范围】
对于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.
【输出】
对于每一个操作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