题解说明

问题背景：
给定一个 $n \times m$ 的网格和 $k$ 个矩形操作。每个矩形由两条对角点 $(x,y)$ 与 $(x_2,y_2)$ 定义。程序使用随机哈希并通过二维前缀异或还原“覆盖编码”，随后枚举上下边界，统计满足条件的子矩形数量。最终输出为满足特定“等编码”约束的子矩形总数。

核心思路：
$1.$ 随机哈希与二维差分：

• 为每个矩形生成一个随机 $60$ 位哈希 $Rd$，并对其两对角点进行异或标记：$mp[x][y]\ \hat{=}\ Rd$，$mp[x_2][y_2]\ \hat{=}\ Rd$。
• 通过二维前缀异或复原编码矩阵：
  $mp[i+1][j+1]\ \hat{=}\ mp[i][j]\ \hat{}\ mp[i+1][j]\ \hat{}\ mp[i][j+1]$。
• 直觉：每个哈希代表一个矩形的身份，异或前缀使得矩形“影响”在矩阵中可累积为列间可比较的编码。

$2.$ 固定上下边界的列编码：

• 枚举上边界 $l$ 与下边界 $r$（要求 $r \ge l+2$，保证高度至少为 $2$）。
• 对每一列 $i$，计算边界之间的编码差：$v[i] = mp[r][i]\ \hat{}\ mp[l][i]$。
• 对于固定 $(l,r)$，若两列 $i$ 与 $j$ 的 $v[i] = v[j]$，则在该行带内以这两列为左右边界的子矩形满足“等编码”约束。

$3.$ 统计等编码的左右列对：

• 将 $v$ 排序后，连续相等段长度为 $L$ 的贡献为所有两两列对的数量 $\binom{L}{2}$。
• 代码中通过线性扫描累计为：当前段长度计数器 $opt$ 每遇到相同元素就把 $ans += opt$ 并令 $opt++$，等价于累加 $\binom{L}{2}$。
• 为避免宽度为 $1$ 的伪计数，额外减去所有相邻列满足 $v[i] = v[i+1]$ 的数量（每次 $ans -= 1$），保证左右边界至少相隔一列。

$4.$ 结果含义与正确性直觉：

• 使用哈希保证不同矩形组合被高概率区分。固定 $(l,r)$ 后，$v[i]$ 表示该带内列 $i$ 的“覆盖编码”。
• $v[i] = v[j]$ 意味着以列 $i,j$ 为边界的子矩形在该带内的覆盖集合一致（异或抵消），符合计数条件。
• 全局枚举所有 $(l,r)$ 汇总得到总子矩形数。

复杂度分析：

• 前缀异或为 $O(nm)$。
• 上下边界枚举约 $O(n^2)$ 次；每次构造 $v$ 为 $O(m)$，排序 $O(m\log m)$，修正相邻约 $O(m)$。
• 总体复杂度近似 $O\big(n^2 \cdot m\log m\big)$，在 $n,m \le 10^3$

#include <bits/stdc++.h>
#define int long long  // 定义int为长整型，避免大数值溢出
using namespace std;

const int N = 1e3 + 10;  // 最大矩阵尺寸（1e3+10，适配题目约束）
int n, m, k;             // n/m：矩阵维度；k：矩形操作次数
int mp[N][N];            // 二维数组：存储异或哈希值，用于标记矩形区域
mt19937 rd(random_device{}());  // 随机数生成器（用于生成哈希标记）

// 处理函数：计算向量f中「连续相等元素段」的贡献值
// 功能：对排序后的f，统计连续相等元素构成的子段中，所有可能的子区间数量
int handle(vector<int> f) {
    sort(f.begin(), f.end());  // 排序：将相同元素聚集，便于统计连续相等段
    int opt = 1;               // 计数器：记录当前连续相等段的长度（初始为1）
    int ans = 0;               // 累计贡献值

    // 遍历排序后的向量（从第2个元素开始）
    for (int i = 1; i < f.size(); i++) {
        if (f[i] != f[i - 1]) {  // 当前元素与前一个不同：结束上一个连续段
            opt = 1;             // 重置计数器
        } else {
            ans += opt;  // 当前元素与前一个相同：累加当前段的贡献（opt为当前段长度）
            opt++;       // 延长连续段长度
        }
    }
    return ans;  // 返回总贡献值
}

signed main() {
    uniform_int_distribution<int> dis(0, (1ll << 60) - 1);  // 随机数分布：生成60位无符号整数
    cin >> n >> m >> k;  // 读取矩阵维度n、m和矩形操作次数k
    n++;  // 维度+1：适配1-based索引（避免边界处理问题）
    m++;

    // 处理k个矩形操作：用随机哈希标记矩形的对角点
    for (int i = 1; i <= k; i++) {
        int x, y, x2, y2;
        cin >> x >> y >> x2 >> y2;  // 读取矩形的两个对角点坐标
        x++, y++, x2++, y2++;       // 坐标+1：转为1-based索引

        int Rd = dis(rd);  // 生成随机哈希值（用于唯一标记当前矩形）
        // 异或标记：矩形的两个对角点添加相同哈希值（二维差分思想）
        mp[x][y] ^= Rd;
        mp[x2][y2] ^= Rd;
    }

    // 计算二维前缀异或：恢复实际的哈希矩阵（逆操作：将对角点标记转化为区域标记）
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            // 异或公式：当前点 = 左上 ^ 上 ^ 左 ^ 当前（类似二维前缀和的逆运算）
            mp[i + 1][j + 1] ^= (mp[i][j] ^ mp[i + 1][j] ^ mp[i][j + 1]);
        }
    }

    int ans = 0;  // 最终答案：统计符合条件的子矩阵数量

    // 枚举所有可能的上下边界（l为上边界，r为下边界，要求r >= l+2，保证子矩阵高度至少2）
    for (int l = 0; l < n; l++) {
        for (int r = l + 2; r <= n; r++) {
            vector<int> v(m + 1);  // 存储列方向的异或结果

            // 计算每一列在上下边界l和r之间的异或值（v[i] = mp[r][i] ^ mp[l][i]）
            for (int i = 0; i <= m; i++) {
                v[i] = (mp[r][i] ^ mp[l][i]);
            }

            // 累加handle函数的结果（统计列方向连续相等段的贡献）
            ans += handle(v);

            // 修正过度计数：减去相邻列异或值相等的情况（过滤无效子矩阵）
            for (int i = 0; i < m; i++) {
                bool opt = ((v[i] ^ v[i + 1]) == 0);  // 相邻列异或值相等标记
                ans -= opt;  // 减去此类情况的计数
            }
        }
    }

    cout << ans << endl;  // 输出最终统计结果
    return 0;
}