题解：矩阵旋转与区间加法维护问题

一、题目核心分析

1. 问题本质

维护一个 $n \times n$ 的矩阵，支持两类操作：

• 旋转操作：对指定正方形子矩阵进行逆时针旋转 90 度；
• 加法操作：对指定矩形子矩阵的所有元素加一个值 $d$（$d$ 可高达 $10^9$）。 最终需计算矩阵所有元素按特定权重（$12345^{(i-1)n+j}$）的加权和。

2. 关键挑战

• 矩阵规模大（$n \leq 3000$），直接暴力处理每个操作会超时（单次旋转/加法操作复杂度 $O(n^2)$，$q=3000$ 时总复杂度 $9 \times 10^9$）；
• 旋转操作针对正方形子矩阵，需高效跟踪矩阵元素的位置变换；
• 加法操作的 $d$ 极大，需避免直接遍历元素累加。

3. 核心思路：分块延迟更新（根号分解）

利用 分块思想，将矩阵的操作延迟处理：

• 维护一个“矩形块”集合，每个块记录其原始区域和当前的变换信息（旋转状态、累加值）；
• 每次操作前，将块分裂到与操作区域完全对齐（确保操作仅作用于完整块）；
• 对符合条件的块，仅更新其变换信息（延迟执行实际旋转/加法）；
• 每经过 $B$ 次操作（$B$ 取根号级别，代码中 $B=50$），统一“重建”矩阵（执行所有延迟的变换，更新实际矩阵元素）。

二、完整代码

#include <bits/stdc++.h>
using namespace std;
const int N = 3005, B = 50, mod = 1000000007, K = 12345;

// 快速加法（模 mod）
inline void add(int &x, int y) {
    x = (x + y) % mod;
}

int n, q, a[N][N]; // a: 实际矩阵
int xl[N], xr[N], yl[N], yr[N]; // 存储每个操作的区域参数
int b[N][N]; // 重建矩阵时的临时存储

// 变换信息结构体：记录块的旋转状态和累加值
struct Info {
    int xx, xy, yx, yy; // 线性变换矩阵（旋转用）
    int xb, yb;         // 线性变换的偏移量（旋转用）
    int d;              // 累加延迟值（加法操作）
    Info() {
        // 初始为单位变换（无旋转，无累加）
        xx = 1, xy = 0, yx = 0, yy = 1;
        xb = 0, yb = 0;
        d = 0;
    }
    // 逆时针旋转 90 度（基于第 id 个操作的区域参数）
    inline void rotate(int id) {
        int _xx = xx, _xy = xy, _yx = yx, _yy = yy;
        int _xb = xb, _yb = yb;
        // 更新线性变换矩阵（逆时针旋转 90 度的线性变换）
        xy = _xx, yy = _yx, yb = _xb - xl[id] + yl[id];
        xx = -_xy, yx = -_yy, xb = -_yb + xl[id] + yr[id];
    }
    // 应用变换：将原始坐标 (x,y) 转换为当前块的实际坐标
    inline void trans(int &x, int &y) {
        int _x = x * xx + y * yx + xb;
        int _y = x * xy + y * yy + yb;
        x = _x, y = _y;
    }
    // 逆变换：将当前块的实际坐标转换为原始坐标（用于分裂块）
    inline void itrans(int &x, int &y) {
        if (xy) {
            int b = yx;
            int g = xx * yy / xy;
            int c = x - xb;
            int h = xx * (y - yb) / xy;
            int e = yy;
            int f = y - yb;
            y = (c - h) / (b - g);
            x = (f - e * y) / xy;
            return;
        }
        int b = xx;
        int g = yx * xy / yy;
        int c = y - yb;
        int h = yx * (x - xb) / yy;
        int e = xy;
        int f = x - xb;
        y = (c - h) / (b - g);
        x = (f - e * y) / yy;
    }
};

// 矩形块结构体：记录块的原始区域和对应的变换信息
struct Square {
    int xl, xr, yl, yr; // 原始区域（未变换前的坐标范围）
    // 应用变换：得到块的当前实际区域
    inline void trans(Info &t) {
        t.trans(xl, yl), t.trans(xr, yr);
        if (xl > xr) swap(xl, xr);
        if (yl > yr) swap(yl, yr);
    }
    // 逆变换：从当前实际区域恢复原始区域
    inline void itrans(Info &t) {
        t.itrans(xl, yl), t.itrans(xr, yr);
    }
};

vector<pair<Square, Info>> vec; // 块集合：每个元素是（原始区域，变换信息）

// 按 x 坐标分裂块：确保所有块的 x 边界与 k 对齐
inline void splitx(int k) {
    int siz = vec.size();
    for (int i = 0; i < siz; i++) {
        auto &e = vec[i].first; // 块的原始区域
        auto f = e;             // 复制原始区域
        auto g = vec[i].second; // 块的变换信息
        f.trans(g);             // 得到块的当前实际区域
        
        // 若当前块的实际区域包含 k（需分裂）
        if (f.xl <= k && k < f.xr) {
            // 分裂为两个块：左块 [f.xl, k]，右块 [k+1, f.xr]
            Square p = {f.xl, k, f.yl, f.yr};
            Square q = {k + 1, f.xr, f.yl, f.yr};
            p.itrans(g); // 恢复为原始区域
            e = p;       // 更新原块为左块
            q.itrans(g); // 恢复为原始区域
            vec.push_back({q, g}); // 添加右块
        }
    }
}

// 按 y 坐标分裂块：确保所有块的 y 边界与 k 对齐
inline void splity(int k) {
    int siz = vec.size();
    for (int i = 0; i < siz; i++) {
        auto &e = vec[i].first;
        auto f = e;
        auto g = vec[i].second;
        f.trans(g);
        
        // 若当前块的实际区域包含 k（需分裂）
        if (f.yl <= k && k < f.yr) {
            // 分裂为两个块：下块 [f.yl, k]，上块 [k+1, f.yr]
            Square p = {f.xl, f.xr, f.yl, k};
            Square q = {f.xl, f.xr, k + 1, f.yr};
            p.itrans(g);
            e = p;
            q.itrans(g);
            vec.push_back({q, g});
        }
    }
}

// 重建矩阵：执行所有延迟的变换，更新实际矩阵 a
inline void rebuild() {
    // 初始化临时矩阵 b
    memset(b, 0, sizeof(b));
    // 遍历所有块，计算每个块对应的实际矩阵元素
    for (auto x : vec) {
        auto p = x.first;  // 块的原始区域
        auto q = x.second; // 块的变换信息
        // 遍历块的原始区域
        for (int i = p.xl; i <= p.xr; i++) {
            for (int j = p.yl; j <= p.yr; j++) {
                int _i = i, _j = j;
                q.trans(_i, _j); // 转换为当前实际坐标
                // 计算元素值：原始值 + 延迟累加值（模 mod）
                b[_i][_j] = (a[i][j] + q.d) % mod;
            }
        }
    }
    // 将临时矩阵 b 复制到实际矩阵 a
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            a[i][j] = b[i][j];
        }
    }
    // 重置块集合：合并为一个完整块（原始区域 [1,n]×[1,n]，无变换）
    vec.clear();
    Square tmp1 = {1, n, 1, n};
    Info tmp2;
    vec.push_back({tmp1, tmp2});
}

int main() {
    scanf("%d %d", &n, &q);
    // 初始化矩阵 a：a[i][j] = (i+1)^j mod 998244353
    for (int i = 1; i <= n; i++) {
        int res = 1, v = i + 1;
        for (int j = 1; j <= n; j++) {
            res = 1ll * res * v % 998244353;
            a[i][j] = res;
        }
    }
    // 初始化块集合：一个完整块
    Square tmp1 = {1, n, 1, n};
    Info tmp2;
    vec.push_back({tmp1, tmp2});
    
    for (int i = 1; i <= q; i++) {
        int op;
        scanf("%d %d %d %d %d", &op, &xl[i], &yl[i], &xr[i], &yr[i]);
        
        // 分裂块：确保所有块的 x 边界与 [xl[i], xr[i]] 对齐
        if (xl[i] - 1) splitx(xl[i] - 1);
        splitx(xr[i]);
        // 分裂块：确保所有块的 y 边界与 [yl[i], yr[i]] 对齐
        if (yl[i] - 1) splity(yl[i] - 1);
        splity(yr[i]);
        
        if (op & 1) { // 操作 1：旋转（逆时针 90 度）
            for (auto &x : vec) {
                auto p = x.first;
                auto q = x.second;
                p.trans(q); // 得到块的当前实际区域
                // 若块的实际区域完全包含在操作区域内，更新旋转状态
                if (xl[i] <= p.xl && p.xr <= xr[i] && yl[i] <= p.yl && p.yr <= yr[i]) {
                    x.second.rotate(i);
                }
            }
        } else { // 操作 2：加法（子矩阵加 d）
            int d;
            scanf("%d", &d);
            for (auto &x : vec) {
                auto p = x.first;
                auto q = x.second;
                p.trans(q); // 得到块的当前实际区域
                // 若块的实际区域完全包含在操作区域内，更新延迟累加值
                if (xl[i] <= p.xl && p.xr <= xr[i] && yl[i] <= p.yl && p.yr <= yr[i]) {
                    add(x.second.d, d);
                }
            }
        }
        
        // 每 B 次操作或最后一次操作，重建矩阵
        if (i % B == 0 || i == q) {
            rebuild();
        }
    }
    
    // 计算最终加权和：sum(A[i][j] * 12345^((i-1)*n + j)) mod mod
    int res = 1, ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            res = 1ll * res * K % mod; // K=12345，累加权重
            add(ans, 1ll * a[i][j] * res % mod); // 累加加权值
        }
    }
    printf("%d", ans);
    return 0;
}

三、关键逻辑详解

1. 块分裂机制（splitx 和 splity）

块分裂的目的是让所有块的边界与当前操作的区域边界对齐，确保操作仅作用于完整的块（避免部分块被操作）。

• 分裂规则：对于操作区域 $[x1, x2] \times [y1, y2]$，需分裂出 $x=x1-1$、$x=x2$、$y=y1-1$、$y=y2$ 四个边界，使所有块的 $x$ 范围要么完全在 $[x1, x2]$ 内，要么完全在外；$y$ 范围同理。
• 坐标变换：分裂时需通过 trans 转换为块的当前实际坐标，判断是否需要分裂；分裂后通过 itrans 恢复为原始坐标，存储在块中。

2. 变换信息结构体（Info）

Info 记录块的两种变换状态，避免直接修改矩阵元素：

• 旋转变换：用线性变换矩阵（$xx, xy, yx, yy$）和偏移量（$xb, yb$）表示逆时针旋转 90 度的效果。旋转操作仅更新这些参数，不实际移动元素。
• 累加延迟：用 d 记录该块的所有加法操作累加值，加法操作仅更新 d，不实际累加元素。

3. 矩阵重建（rebuild）

每经过 $B$ 次操作（$B=50$），执行一次重建：

• 遍历所有块，根据块的原始区域和变换信息，计算每个元素的实际值（原始值 + 延迟累加值），存储到临时矩阵 b；
• 将 b 复制到实际矩阵 a，完成延迟操作的执行；
• 重置块集合为一个完整块，准备下一轮延迟操作。

4. 初始矩阵与最终加权和

• 初始矩阵：$a[i][j] = (i+1)^j \mod 998244353$，通过递推计算（每次乘 $(i+1)$ 取模）。
• 最终加权和：权重为 $12345^{(i-1)n+j}$，通过递推累加权重（每次乘 12345 取模），再累加每个元素的加权值。

四、复杂度分析

• 块分裂复杂度：每次分裂操作最多新增 $O(n)$ 个块，但由于每 $B$ 次操作后重建（块数重置为 1），总分裂次数为 $O(qB)$。$B=50$，$q=3000$ 时，总分裂次数为 $1.5 \times 10^5$，每次分裂的块数为 $O(B)$（重建后块数为 1，分裂后块数最多 $O(B)$），故分裂总复杂度为 $O(qB^2) = 7.5 \times 10^6$。
• 重建复杂度：每次重建需遍历整个矩阵，复杂度 $O(n^2)$。重建次数为 $O(q/B) = 60$，总重建复杂度为 $O(qn^2/B) = 60 \times 9 \times 10^6 = 5.4 \times 10^8$（可通过常数优化通过）。
• 总复杂度：$O(qB^2 + qn^2/B)$，当 $B$ 取 $\sqrt{n}$（约 55）时，复杂度最优，适配 $n=3000$、$q=3000$ 的数据范围。

总结

本题的核心是利用 分块延迟更新 思想，将高频操作（旋转、加法）转化为对块的变换信息更新，避免直接操作大规模矩阵。关键在于：

1. 设计合理的块分裂机制，确保操作仅作用于完整块；
2. 用线性变换和延迟累加记录块的状态，减少重复计算；
3. 选择合适的重建间隔 $B$，平衡分裂和重建的复杂度。