526互联

P9286 [ROI 2018] Extraction of radium

发布时间 2023-06-07 18:20:24作者: 朝绾曦梦

来一发简单做法

题目链接：P9286 [ROI 2018] Extraction of radium

通过读题目，我们不难想到，找到既是横向最大值又是纵行最大值的位置，可以单独处理横向和纵向，满足一个方向的最大值就标记一次，那么标记两次的位置就是当前局面的一个可行点。这样静态操作就明晰了。

现在考虑动态操作，把一个点的值改的比之前大，如果之前这个点事可行的，改的更大之后一定依旧满足。如果之前不是可行点，可是现在比所在列的最大值大，或者比所在行的最大值大，那么就更新标记。

更新标记的操作无非就是把之前的标记抹去，添加新标记，用 \(x\) 数组储存每一行的最大值所在列，用 \(y\) 数组储存每一列的最大值所在行，更新一下 \(x\) 数组和 \(y\) 数组即可。

这里使用动态数组来实现，注意下标。

见代码：

#include<iostream>
#include<cstdio>
#include<queue>
#include<cmath>
#include<cstring>
#include<vector>
using namespace std;
int x[200001],y[200001];
vector<int>a[200001];
vector<int>vis[200001];
int main()
{
    int n, m, q, ans = 0;
    scanf("%d%d%d",&n, &m, &q);
    for(int i = 0;i <= n - 1; i++){
        a[i].resize(m,0);
        vis[i].resize(m,0);
        for(int j = 0;j <= m - 1; j++){
            scanf("%d",&a[i][j]);
            if(a[i][j] > a[i][x[i]]){
                x[i] = j;
            }
            if(a[i][j] > a[y[j]][j]){
                y[j] = i;
            }
        }
    }
    for(int i = 0;i <= n - 1; i++){
        vis[i][x[i]]++;
    }
    for(int j = 0;j <= m-1; j++){
        vis[y[j]][j]++;
    }
    for(int i = 0;i <= n - 1; i++){
        for(int j = 0;j <= m - 1; j++){
           if(vis[i][j] == 2) ans++; 
        }
    }
    for(int i, j, w, o = 1;o <= q; o++){
        scanf("%d%d%d",&i, &j, &w);
        i--;
        j--;
        a[i][j] = w;
        if(vis[i][j] == 2)
        {
            printf("%d\n",ans);
            continue;
        }
        if(a[i][j] > a[i][x[i]]){
            if(vis[i][x[i]] == 2){
                ans--;
            }
            vis[i][x[i]]--;
            x[i] = j;
            vis[i][x[i]]++;
            if(vis[i][x[i]] == 2){
                ans++;
            }
        }
        if(a[i][j] > a[y[j]][j]){
            if(vis[y[j]][j] == 2){
                ans--;
            }
            vis[y[j]][j]--;
            y[j] = i;
            vis[y[j]][j]++;
            if(vis[y[j]][j] == 2){
                ans++;
            }
        }
        printf("%d\n",ans);
    }
	return 0;
}