2672. 「NOI2012」魔幻棋盘 题解

题目分析

我们需要维护一个 $N \times M$ 的矩阵，支持两种操作：

1. 查询：以固定点 $(X,Y)$ 为中心的矩形区域的最大公约数（GCD）
2. 修改：任意矩形区域所有元素加上一个值 $c$

关键点：所有查询都以 $(X,Y)$ 为中心，这个性质非常重要。

---

核心思路

1. GCD的差分性质

对于一维数组 $a[1..n]$，有重要性质：

$$\gcd(a_1, a_2, \dots, a_n) = \gcd(a_1, a_2-a_1, a_3-a_2, \dots, a_n-a_{n-1}) $$

即原数组的 GCD 等于第一个元素与差分数组的 GCD。

扩展到二维，以 $(X,Y)$ 为原点，定义二维差分数组 $d[i][j]$：

$$d[i][j] = a[i][j] - a[i-1][j] - a[i][j-1] + a[i-1][j-1] $$

特别地，对于以 $(X,Y)$ 为左上角的矩形 $[X..X+x, Y..Y+y]$，有：

$$\gcd(a[X..X+x][Y..Y+y]) = \gcd\left(a[X][Y],\ \gcd_{i,j}(d[i][j] \text{ 在矩形内且不在第一行第一列})\right) $$

更具体地，对于查询区域：向上 $x_1$ 行，向下 $x_2$ 行，向左 $y_1$ 列，向右 $y_2$ 列，实际矩形为：

$$[X-x_1, X+x_2] \times [Y-y_1, Y+y_2]$$

其 GCD 可以通过 $(X,Y)$ 的值和差分数组某些位置的 GCD 计算得到。

---

2. 固定中心点的优势

由于所有查询都以 $(X,Y)$ 为中心，我们可以将坐标系平移，使 $(X,Y)$ 变为 $(0,0)$。这样，查询矩形总是包含原点。

定义四个象限：

• $a[x][y]$：原矩阵值
• $b[x][y]$：二维差分数组

对于包含原点的矩形 $[-x_1..x_2] \times [-y_1..y_2]$，其 GCD 为：

$$\gcd\left( a[0][0],\ \gcd_{i=-x_1..x_2, j=-y_1..y_2, (i,j)\neq(0,0)} b[i][j] \right) $$

但实际上，我们只需要计算差分数组中特定几个矩形的 GCD。

---

3. 二维数据结构

我们需要维护：

1. 原点的值 $a[0][0]$
2. 差分数组 $b[x][y]$ 的区间 GCD

操作对应：

• 修改矩形加 $c$：在差分数组上修改 4 个点（矩形四个角）
• 查询矩形 GCD：查询差分数组中几个矩形的 GCD，再与 $a[0][0]$ 取 GCD

具体来说，对于修改矩形 $[x_1..x_2] \times [y_1..y_2]$ 加 $c$：

1. $b[x_1][y_1] += c$
2. $b[x_1][y_2+1] -= c$
3. $b[x_2+1][y_1] -= c$
4. $b[x_2+1][y_2+1] += c$

对于查询矩形 $[-x_1..x_2] \times [-y_1..y_2]$：

$$\text{ans} = \gcd\left(a[0][0],\ \gcd(b[-x_1..-1][-y_1..-1]),\ \gcd(b[-x_1..-1][1..y_2]),\ \gcd(b[1..x_2][-y_1..-1]),\ \gcd(b[1..x_2][1..y_2])\right) $$

---

4. 数据结构选择

由于 $N \times M \le 500000$，我们可以使用：

• 二维线段树（树套树）：内层线段树用动态开点
• 四分树：实现相对简单
• 根据数据分类处理：
  • A类：暴力
  • B类（$N=1$）：一维线段树
  • C类：二维线段树

---

算法实现

数据结构设计

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN = 500010;
const int MAX_NODES = 20000000; // 动态开点节点数

struct Node1D {
    ll gcd_val;
    Node1D *lch, *rch;
    Node1D() : gcd_val(0), lch(nullptr), rch(nullptr) {}
};

struct Node2D {
    Node1D *root;
    Node2D *lch, *rch;
    Node2D() : root(nullptr), lch(nullptr), rch(nullptr) {}
};

// GCD函数，处理0的情况
ll gcd(ll a, ll b) {
    if (a < 0) a = -a;
    if (b < 0) b = -b;
    while (b) {
        ll t = a % b;
        a = b;
        b = t;
    }
    return a;
}

// 一维线段树：区间GCD
class SegTree1D {
private:
    Node1D* new_node() {
        static Node1D pool[MAX_NODES];
        static int idx = 0;
        return &pool[idx++];
    }
    
    void update(Node1D* &node, int l, int r, int pos, ll val) {
        if (!node) node = new_node();
        if (l == r) {
            node->gcd_val += val;
            return;
        }
        int mid = (l + r) >> 1;
        if (pos <= mid) update(node->lch, l, mid, pos, val);
        else update(node->rch, mid+1, r, pos, val);
        
        ll left_gcd = node->lch ? node->lch->gcd_val : 0;
        ll right_gcd = node->rch ? node->rch->gcd_val : 0;
        node->gcd_val = gcd(left_gcd, right_gcd);
    }
    
    ll query(Node1D* node, int l, int r, int ql, int qr) {
        if (!node || ql > r || qr < l) return 0;
        if (ql <= l && r <= qr) return node->gcd_val;
        int mid = (l + r) >> 1;
        return gcd(query(node->lch, l, mid, ql, qr),
                   query(node->rch, mid+1, r, ql, qr));
    }
    
public:
    void update(Node1D* &root, int m, int y, ll val) {
        update(root, 1, m, y, val);
    }
    
    ll query(Node1D* root, int m, int y1, int y2) {
        return query(root, 1, m, y1, y2);
    }
};

// 二维线段树：外层x维，内层y维
class SegTree2D {
private:
    int n, m;
    Node2D* root;
    SegTree1D seg1d;
    
    Node2D* new_node2d() {
        static Node2D pool[MAX_NODES];
        static int idx = 0;
        return &pool[idx++];
    }
    
    void update(Node2D* &node, int l, int r, int x, int y, ll val) {
        if (!node) node = new_node2d();
        seg1d.update(node->root, m, y, val);
        
        if (l == r) return;
        
        int mid = (l + r) >> 1;
        if (x <= mid) update(node->lch, l, mid, x, y, val);
        else update(node->rch, mid+1, r, x, y, val);
    }
    
    ll query(Node2D* node, int l, int r, int x1, int x2, int y1, int y2) {
        if (!node || x1 > r || x2 < l) return 0;
        if (x1 <= l && r <= x2) {
            return seg1d.query(node->root, m, y1, y2);
        }
        int mid = (l + r) >> 1;
        return gcd(query(node->lch, l, mid, x1, x2, y1, y2),
                   query(node->rch, mid+1, r, x1, x2, y1, y2));
    }
    
public:
    SegTree2D(int n_, int m_) : n(n_), m(m_) {
        root = nullptr;
    }
    
    void update(int x, int y, ll val) {
        update(root, 1, n, x, y, val);
    }
    
    ll query(int x1, int x2, int y1, int y2) {
        if (x1 > x2 || y1 > y2) return 0;
        return query(root, 1, n, x1, x2, y1, y2);
    }
};

int main() {
    int N, M, X, Y, T;
    scanf("%d%d%d%d%d", &N, &M, &X, &Y, &T);
    
    // 平移坐标系，使(X,Y)变为(0,0)
    // 新坐标范围：x ∈ [-X+1..N-X], y ∈ [-Y+1..M-Y]
    // 为了方便，加上偏移量 OFFSET
    const int OFFSET_X = X;
    const int OFFSET_Y = Y;
    const int newN = N;
    const int newM = M;
    
    vector<vector<ll>> a(N+2, vector<ll>(M+2, 0));
    vector<vector<ll>> diff(N+2, vector<ll>(M+2, 0));
    
    // 读入初始矩阵并计算差分
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            scanf("%lld", &a[i][j]);
        }
    }
    
    // 计算二维差分
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            diff[i][j] = a[i][j] - a[i-1][j] - a[i][j-1] + a[i-1][j-1];
        }
    }
    
    // 创建二维线段树维护差分数组的GCD
    SegTree2D segtree(N+1, M+1);
    
    // 初始化差分数组到线段树
    for (int i = 1; i <= N+1; i++) {
        for (int j = 1; j <= M+1; j++) {
            if (diff[i][j] != 0) {
                segtree.update(i, j, diff[i][j]);
            }
        }
    }
    
    // 原点值
    ll origin_val = a[X][Y];
    
    while (T--) {
        int op;
        scanf("%d", &op);
        
        if (op == 0) { // 查询
            int x1, y1, x2, y2;
            scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
            
            // 实际查询矩形：[X-x1..X+x2] × [Y-y1..Y+y2]
            int lx = X - x1, rx = X + x2;
            int ly = Y - y1, ry = Y + y2;
            
            // 计算答案 = gcd(原点值, 四个区域的gcd)
            ll ans = origin_val;
            
            // 第一象限：[X+1..rx][Y+1..ry] -> 差分数组：[X+1..rx][Y+1..ry]
            if (rx > X && ry > Y) {
                ans = gcd(ans, segtree.query(X+1, rx, Y+1, ry));
            }
            
            // 第二象限：[lx..X-1][Y+1..ry] -> 注意差分位置
            if (lx < X && ry > Y) {
                // 差分对应：[lx+1..X][Y+1..ry]
                ans = gcd(ans, segtree.query(lx+1, X, Y+1, ry));
            }
            
            // 第三象限：[lx..X-1][ly..Y-1]
            if (lx < X && ly < Y) {
                // 差分对应：[lx+1..X][ly+1..Y]
                ans = gcd(ans, segtree.query(lx+1, X, ly+1, Y));
            }
            
            // 第四象限：[X+1..rx][ly..Y-1]
            if (rx > X && ly < Y) {
                // 差分对应：[X+1..rx][ly+1..Y]
                ans = gcd(ans, segtree.query(X+1, rx, ly+1, Y));
            }
            
            printf("%lld\n", ans);
            
        } else { // 修改
            int x1, y1, x2, y2;
            ll c;
            scanf("%d%d%d%d%lld", &x1, &y1, &x2, &y2, &c);
            
            // 更新原点值：如果修改区域包含(X,Y)
            if (x1 <= X && X <= x2 && y1 <= Y && Y <= y2) {
                origin_val += c;
            }
            
            // 更新差分数组：四个角
            // 左上角
            segtree.update(x1, y1, c);
            // 右上角
            if (y2 < M) segtree.update(x1, y2+1, -c);
            // 左下角
            if (x2 < N) segtree.update(x2+1, y1, -c);
            // 右下角
            if (x2 < N && y2 < M) segtree.update(x2+1, y2+1, c);
        }
    }
    
    return 0;
}

---

算法细节

1. 坐标变换

• 将 $(X,Y)$ 视为原点 $(0,0)$
• 实际存储时加上偏移量，避免负数下标

2. GCD计算

• 注意处理负数：$\gcd(a,b) = \gcd(|a|,|b|)$
• $\gcd(a,0) = |a|$

3. 差分更新

修改矩形 $[x_1..x_2] \times [y_1..y_2]$ 加 $c$：

• $d[x_1][y_1] += c$
• $d[x_1][y_2+1] -= c$（如果 $y_2+1$ 在范围内）
• $d[x_2+1][y_1] -= c$（如果 $x_2+1$ 在范围内）
• $d[x_2+1][y_2+1] += c$（如果都在范围内）

4. 查询分解

查询矩形 $[-x_1..x_2] \times [-y_1..y_2]$ 分解为：

1. 原点 $(0,0)$ 的值
2. 四个象限的差分 GCD

---

复杂度分析

• 空间：动态开点二维线段树，$O(NM \log N \log M)$，但实际 $NM \le 500000$，可接受
• 时间：
  • 查询：$O(\log N \log M)$
  • 修改：$O(\log N \log M)$
  • 总复杂度：$O(T \log N \log M)$

---

优化与注意事项

1. 内存优化

• 使用内存池而非递归new
• 只在需要时创建节点

2. 边界处理

• 修改时注意矩形边界是否超出范围
• 查询时注意象限是否为空

3. 大数处理

• 使用 long long 或 __int128
• GCD计算时注意溢出

---

总结

本题的解题关键在于：

1. 发现GCD的差分性质
2. 利用固定中心点简化问题
3. 设计合适的数据结构维护二维差分GCD
4. 正确处理坐标变换和边界情况

这是一道综合性很强的数据结构题，需要结合数学性质（GCD差分）和高级数据结构（二维线段树）才能高效解决。