矩阵行列最大值计数问题（Radium Extraction）题解

本题核心是高效处理矩阵元素修改后，统计“既是所在行最大值，又是所在列最大值”的元素数量。利用“每次修改仅增大元素值”的特性，可通过跟踪行列最大值位置，用集合维护目标元素，实现高效查询。

一、问题分析

1. 核心需求：每次将矩阵某位置元素改为更大值后，统计“行列双最大值”的元素个数。
2. 关键特性：矩阵元素互不相同，且修改仅增大数值，这意味着每行/列的最大值只会被新的更大值替换，不会回溯。
3. 效率要求：面对最大 $2 \times 10^5$ 的矩阵规模和查询次数，需避免每次查询遍历整个矩阵，必须优化时间复杂度。

二、核心思路

1. 跟踪行列最大值：用数组分别存储每行的最大值（Rmax）及其列位置（Rpos）、每列的最大值（Cmax）及其行位置（Cpos）。
2. 维护目标元素集合：用集合（set）存储“行列双最大值”的位置，集合大小即为每次查询的答案。
3. 修改时的更新逻辑：
   • 若修改后的值成为所在行的新最大值，需移除原行最大值的位置（若在集合中），并更新行最大值信息。
   • 若修改后的值成为所在列的新最大值，同理移除原列最大值的位置，更新列最大值信息。
   • 最后检查修改位置是否成为新的“行列双最大值”，若是则加入集合。

三、完整代码实现

#ifndef M_DEBUG
#define NDEBUG 1
#define FAST_IO 1

#define D(x) ({ void(0); })
#else
#define D(x) ({ auto t = (x); cerr << "| DEBUG #" << __LINE__ << " IN " << __FUNCTION__ << "() \t| \t" << #x << " = \t[" << t << "]\n"; void(0); })
#endif

#include <bits/stdc++.h>

#ifdef __linux__
#include <bits/extc++.h>
#define gc() getchar_unlocked()
#else
#include <ext/rope>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/priority_queue.hpp>
#include <ext/pb_ds/exception.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <ext/pb_ds/list_update_policy.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/trie_policy.hpp>
#define gc() getchar()
#endif

using namespace std;

#ifdef FAST_IO
#define endl "\n"
#endif

template<typename T>
T read() {
    T n = 0;
    int f = 0, c = gc();

    for (; !isdigit(c); c = gc())
        f |= c == '-';

    for (; isdigit(c); c = gc())
        n = n * 10 + c - '0';

    return f ? -n : n;
}

mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());

template<typename T, typename CMP = less<T>>
using pqueue = __gnu_pbds::priority_queue<T, CMP>;
// using pqueue = priority_queue<T, vector<T>, CMP>;

// -----------------------------------------------------------------------------

constexpr int N = 2e5 + 10;

int n, m, q;

vector<vector<int>> a;  // 存储矩阵元素（1-based索引）
int Rmax[N];            // Rmax[i]：第i行的最大值
int Rpos[N];            // Rpos[i]：第i行最大值的列位置
int Cmax[N];            // Cmax[j]：第j列的最大值
int Cpos[N];            // Cpos[j]：第j列最大值的行位置
set<pair<int, int>> bucket;  // 存储“行列双最大值”的位置（i,j）

void Main() {
    // 读取矩阵规模和查询次数
    cin >> n >> m >> q;
    a.resize(n + 1, vector<int>(m + 1));  // 初始化1-based矩阵

    // 读取矩阵元素
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            cin >> a[i][j];

    // 初始化每行的最大值和位置
    for (int i = 1; i <= n; ++i) {
        Rmax[i] = -1;  // 初始值设为极小（矩阵元素≥1）
        for (int j = 1; j <= m; ++j) {
            if (a[i][j] > Rmax[i]) {
                Rmax[i] = a[i][j];
                Rpos[i] = j;
            }
        }
    }

    // 初始化每列的最大值和位置
    for (int j = 1; j <= m; ++j) {
        Cmax[j] = -1;  // 初始值设为极小
        for (int i = 1; i <= n; ++i) {
            if (a[i][j] > Cmax[j]) {
                Cmax[j] = a[i][j];
                Cpos[j] = i;
            }
        }
    }

    // 初始化“行列双最大值”集合
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            if (a[i][j] == Rmax[i] && a[i][j] == Cmax[j])
                bucket.emplace(i, j);

    // 处理每次修改查询
    while (q--) {
        int x, y, t;  // 修改位置（x行y列），新值t
        cin >> x >> y >> t;

        // 1. 检查是否成为所在行的新最大值
        if (t > Rmax[x]) {
            // 移除原行最大值的位置（若在集合中）
            bucket.erase({x, Rpos[x]});
            // 更新行最大值和位置
            Rmax[x] = t;
            Rpos[x] = y;
        }

        // 2. 检查是否成为所在列的新最大值
        if (t > Cmax[y]) {
            // 移除原列最大值的位置（若在集合中）
            bucket.erase({Cpos[y], y});
            // 更新列最大值和位置
            Cmax[y] = t;
            Cpos[y] = x;
        }

        // 3. 检查当前位置是否为“行列双最大值”，若是则加入集合
        if (t == Rmax[x] && t == Cmax[y])
            bucket.emplace(x, y);

        // 集合大小即为当前答案
        cout << bucket.size() << endl;
    }
}

// -----------------------------------------------------------------------------

signed main() {
    //  freopen("matrix.in", "r", stdin);
    //  freopen("matrix.out", "w", stdout);
#ifdef FAST_IO
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
#endif
    Main();
    return 0;
}

四、代码解析

1. 数据结构说明

2. 关键步骤拆解

（1）初始化阶段

• 行列最大值计算：遍历每行/列，找到初始的最大值及其位置，时间复杂度 $O(nm)$。
• 目标集合初始化：遍历矩阵，将同时满足“行最大值”和“列最大值”的位置加入集合，时间复杂度 $O(nm)$。

（2）修改查询阶段

每次查询处理逻辑（时间复杂度 $O(\log k)$，$k$ 为集合中元素个数，最坏 $O(\log nm)$）：

1. 行最大值更新：若新值大于当前行最大值，移除原行最大值的位置（若在集合中），更新行最大值信息。
2. 列最大值更新：同理处理列最大值的更新。
3. 目标集合维护：检查修改位置是否成为新的“行列双最大值”，若是则加入集合。
4. 输出答案：集合大小即为当前“行列双最大值”的个数，直接输出。

五、复杂度分析

• 初始化：$O(nm)$，仅需遍历矩阵2次（计算行列最大值+初始化集合）。
• 单次查询：$O(\log nm)$，核心操作是集合的插入/删除，均为对数时间。
• 总复杂度：$O(nm + q\log nm)$，可满足 $n,m,q \leq 2 \times 10^5$ 的数据规模要求。