十字架

【题目描述】：

给你一个N*M的网格，每个格子上都着了色，你的任务是计算某一特定颜色的十字架的数量。我们称在(x,y)位置存在一个大小为k(k>0)的十字架，是指十字架上所有的单元都在第x行或者在第y列，并且到(x,y) 的距离在k以内，并且都和(x,y)位置具有相同的颜色。注意具有相同中心位置但不同大小的十字架看作是不同的。不幸的是单元格的颜色是不断变化的。

【输入格式】：

第一行4个整数N,M,C,Q(1<=N,M,C<=100,1<=Q<=10000)

接下来N行，每行M个1到C之间的整数描述单元格的颜色。

接下来Q行每行或者是”C i j k”的形式表示把(i,j)位置的颜色变为k,或者是”Q c”的形式表示询问颜色为c的十字架的数量。(1<=i<=N,1<=j<=M,1<=k,c<=C)

【输出格式】：

    对于每次询问输出询问颜色对应的十字架的数量。

【样例输入】：

5 5 3 6

1 3 2 3 1

3 3 2 3 3

2 2 2 2 2

3 3 2 3 3

1 3 2 3 1

Q 1

Q 2

Q 3

C 2 3 3

C 3 2 3

Q 3

【样例输出】：

0

2

0

1

解题：这题最朴素的做法就是模拟。如果直接模拟，插入的时间复杂度为O(1)，询问的时间复杂度为O(N^2*k)，最坏的情况下，总时间复杂度为O(10000*N^2*k)，对于极限数据，必然超时。显然，要AC必须要降低查询的复杂度。用f[I,j,k]表示I,j这个格子，在方向k中有多少个连续的数和I,j这个格子的数相等。1<=k<=4，分别表示上，右，下，左。用sum[i]表示第i种颜色的十字架有多少个。因为每修改一个点，只对以这个点为中心的“十”字范围内有影响，所以在修改时，“十”字范围内的f[I,j,k]就可以了。那么插入的复杂度最坏是O(200)，而输出的复杂度变为O(1)，比原来的复杂度降了许多，这样就可以AC了……