解题思路

这道题要求在动态变化的网格中计算特定颜色的十字图案数量。解题的关键在于高效维护和查询十字图案：

1. 十字图案定义：以某个点为中心，上下左右四个方向延伸相同距离k的所有格子颜色相同
2. 预处理与维护：
   • 每个格子维护一个值b[i][j]，表示以该点为中心的最大十字大小
   • 数组c[k]维护颜色为k的所有十字数量总和
3. 动态更新：当某个格子颜色改变时，不仅更新该点的十字值，还需更新其所在行列的所有格子

题意分析

本题模拟一个动态变化的网格，需要处理两种操作：

• 修改操作(C)：将某个格子的颜色修改为指定值
• 查询操作(Q)：查询当前网格中特定颜色的十字图案总数

关键点：

• 十字图案的大小可以不同，只要中心相同即视为不同图案
• 修改操作可能影响同一行和列的所有格子的十字值
• 需要高效处理大量查询和修改操作

标程实现

以下是完整的标程实现，包含详细注释：

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
int a[110][110], b[110][110], c[110];  // a:颜色, b:十字大小, c:颜色计数
int N, M, C, Q, x, y, z;
char op[2];

// 判断坐标是否在网格内
bool inMap(int x, int y){
    return x > 0 && x <= N && y > 0 && y <= M;
}

// 检查以(x,y)为中心，大小为k的十字是否存在
bool check(int x, int y, int k){
    if (!inMap(x + k, y) || a[x + k][y] != a[x][y]) return 0;
    if (!inMap(x, y + k) || a[x][y + k] != a[x][y]) return 0;
    if (!inMap(x - k, y) || a[x - k][y] != a[x][y]) return 0;
    if (!inMap(x, y - k) || a[x][y - k] != a[x][y]) return 0;
    return 1;
}

// 计算以(x,y)为中心的最大十字大小，并返回十字数量
int add(int x, int y){
    int ans = 0;
    for (int i = 1; i <= 210; i++)  // 枚举可能的十字大小
        if (check(x, y, i)) ans += 1;
        else break;  // 一旦不满足条件，后续更大的k也不可能满足
    return ans;
}

// 处理颜色修改操作
void change(int x, int y, int cc){
    if (a[x][y] == cc) return;  // 颜色未改变，无需处理
    
    // 从原颜色计数中减去当前十字值
    c[a[x][y]] -= b[x][y];
    
    // 更新颜色
    a[x][y] = cc;
    
    // 重新计算并更新当前点的十字值
    b[x][y] = add(x, y);
    c[a[x][y]] += b[x][y];
    
    // 更新同一列的所有点
    for (int i = 1; i <= N; i++){
        if (i == x) continue;  // 跳过已处理的点
        c[a[i][y]] -= b[i][y];
        b[i][y] = add(i, y);
        c[a[i][y]] += b[i][y];
    }
    
    // 更新同一行的所有点
    for (int i = 1; i <= M; i++){
        if (i == y) continue;  // 跳过已处理的点
        c[a[x][i]] -= b[x][i];
        b[x][i] = add(x, i);
        c[a[x][i]] += b[x][i];
    }
}

// 初始化所有格子的十字值
void init(){
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= M; j++){
            b[i][j] = add(i, j);
            c[a[i][j]] += b[i][j];
        }
}

// 处理所有输入和查询
void solve(){
    memset(c, 0, sizeof(c));
    memset(a, 0, sizeof(a));
    
    // 读取初始网格
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= M; j++)
            scanf("%d", &a[i][j]);
    
    // 初始化十字值
    init();
    
    // 处理所有查询
    while(Q--){
        scanf("%s", op);
        if (op[0] == 'C'){  // 修改操作
            scanf("%d%d%d", &x, &y, &z);
            change(x, y, z);
        }else{  // 查询操作
            scanf("%d", &x);
            printf("%d\n", c[x]);
        }
    }
}

int main(){
    while(scanf("%d%d%d%d", &N, &M, &C, &Q) == 4) solve();
    return 0;
}

代码解释

1. 预处理阶段：

   • init函数：计算每个格子的最大十字大小，并统计每种颜色的十字总数
   • add函数：枚举可能的十字大小，直到不满足条件为止

2. 修改操作处理：

   • change函数：当某个格子颜色改变时，更新该点及其所在行列的所有格子的十字值
   • 先从原颜色计数中减去旧值，再计算新值并添加到新颜色计数中

3. 查询操作处理：

   • 直接通过数组c返回对应颜色的十字总数
   • 由于预处理和修改操作中已经维护了正确的计数，查询操作时间复杂度为O(1)

该实现通过预处理和动态维护，确保在合理时间内处理大量查询和修改操作，满足题目要求。