#P4054. [JSOI2009] 计数问题

    ID: 4552 远端评测题 1000ms 128MiB 尝试: 5 已通过: 2 难度: 10 上传者: 标签>2009各省省选树状数组江苏前缀和概率论,统计

[JSOI2009] 计数问题

题目描述

一个 n× mn \times\ m 的方格,初始时每个格子有一个整数权值。接下来每次有 2 种操作:

  • 改变一个格子的权值;

  • 求一个子矩阵中某种特定权值出现的个数。

输入格式

第一行有两个数 n,mn,m

接下来 nn 行,每行 mm 个数,第 i+1i+1 行第 jj 个数表示格子 (i,j)(i,j) 的初始权值。

接下来输入一个整数 QQ

之后 QQ 行,每行描述一个操作。

操作 1:输入一行四个整数 1 x y c1\ x\ y\ c,表示将格子 (x,y)(x,y) 的权值改成 cc

操作 2:输入一行六个整数 2 x1 x2 y1 y2 c2\ x_1\ x_2\ y_1\ y_2\ c。表示询问所有满足格子颜色为 cc,且满足 x1xx2,y1yy2x_1\le x\le x_2,y_1\le y\le y_2 的格子个数。

输出格式

对于每个操作 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%30\% 的数据,满足:n,m30n,m\le 30Q5×104Q\le 5\times 10^4

对于 100%100\% 的数据,满足:1n,m3001\le n,m\le 3001Q2×1051\le Q\le 2\times 10^5

对于操作 1,保证:1xn1\le x \le n1ym1\le y\le m1c1001\le c\le 100

对于操作 2,保证:1x1x2n1\le x_1≤x_2\le n1y1y2m1\le y_1\le y_2\le m1c1001\le c\le 100