P9286 [ROI 2018] Extraction of radium题解

· · 题解

P9286 [ROI 2018] Extraction of radium

题面

link

思路

sub1 暴力

对于每一次修改，遍历整个矩阵来计算满足要求的点的个数。

时间复杂度 O(nmq)。能通过 subtask 1，2。

期望得分 50pts。

sub2 正解

由题意可得，一行（列）中满足要求的点最多只有一个。

借此，我们可以想到去维护一些东西。

首先，使用两个数组 row 和 col 维护每行每列的最大值，很明显，满足要求的点 (i，j) 满足第 i 行第 j 列最大值相等，即 row_i=col_j。

借此，我们便可以统计出初始矩阵的答案个数。

考虑动态维护答案。

可以注意到当修改一个点 (i，j) 时，只会改变第 i 行与第 j 列的最大值。即答案最多只会改变 2。

于是我们可以分几种情况：

  1. 第 i 行与第 j 列上没有满足要求的点。这时单独判断修改后的点是否能算入贡献。
  2. 第 i 行上有满足要求的点，如果这个点修改后大于本行最大值，那么原本那个点就失效了，答案减一。
  3. 第 j 行上有满足要求的点，如果这个点修改后大于本列最大值，那么原本那个点就失效了，答案同样减一。
  4. 修改的点就是第 i 行与第 j 列上满足要求的点，先将答案减一，在后续判断中再加起来。

因为数字越改越大，所以以上四种情况以及对应修改答案的方法是成立的。

于是我们就可以维护每行每列对答案贡献的状况，以及与此行满足要求的点相对应的列与此列满足要求的点相对应的行数来达到记录满足条件的点及修改的功能。

代码如下：

// by MornStar
// 2023.5.26
#include<bits/stdc++.h>
using namespace std;
int row[200005],col[200005],ma1[200005],ma2[200005],ans;
bool r[200005],c[200005];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n,m,q;
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++){
        for(int j=1,k;j<=m;j++){
            cin>>k;
            row[i]=max(row[i],k);
            col[j]=max(col[j],k);
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(row[i]==col[j]){
                ans++;
                r[i]=c[j]=1;
                ma1[i]=j;
                ma2[j]=i;
            }
        }
    }
    for(int i=1;i<=q;i++){
        int cx,cy,val;
        cin>>cx>>cy>>val;
        if(ma1[cx]==cy) ans--;
        if(val>row[cx]){
            row[cx]=val;
            if(r[cx]==1&&ma1[cx]!=cy){
                r[cx]=c[ma1[cx]]=0;
                ma2[ma1[cx]]=0;
                ma1[cx]=0;
                ans--;
            }
        }
        if(val>col[cy]){
            col[cy]=val;
            if(c[cy]==1&&ma2[cy]!=cx){
                c[cy]=r[ma2[cy]]=0;
                ma1[ma2[cy]]=0;
                ma2[cy]=0;
                ans--;
            }
        }
        if(row[cx]==col[cy]){
            ans++;
            r[cx]=c[cy]=1;
            ma1[cx]=cy;
            ma2[cy]=cx;
        }
        cout<<ans<<endl;
    }
}

时间复杂度 O(nm+q)，期望得分 100pts。