H 时不时使使用玉米加农炮掩饰害羞的邻座艾莉同学

解题思路

本来想用优先队列，map啥的，然后想存坐标用值维护，但脑子一抽，觉得值可能会相同，就不知道改该怎么写了。

然后突然发现： , 即，也就是说，完全可以直接存图。那么每一次增援时（增援的敌人数量记为），我们把所能影响的格子修改，加上自己这一格，总共一次修改13个格子，也就是代码中的部分。而每次增援后的最大值只会从当前的最大值和修改后的值中出现，我们只要记录最大值的坐标即可。时间复杂度为。

代码

#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define endl '\n'
#define pii pair<int,int>
using namespace std;
const int N = 502;
int a[N][N];
//曼哈顿距离不超过2的所有坐标,包括自己
int dx[13] = {-2, -1, -1, -1, 0, 0, 0, 0,  0,  1, 1, 1, 2};
int dy[13] = { 0,  1,   0, -1, 2, 1, 0, -1, -2, 1, 0, -1, 0};
void solve()
{
    int n, m, q;
    cin >> n >> m >> q; 
    int mx, my, maxn = 0;
    for(int i = 1, v; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            cin >> v;
            for(int k = 0; k < 13; k++)
            {
                //影响的格子坐标(nx,ny)
                int nx = i + dx[k], ny = j + dy[k];
                if(nx >= 1 && nx <= n && ny >= 1 && ny <= m) 
                {     
                    a[nx][ny] += v;
                    if(a[nx][ny] > maxn)
                    {
                        maxn = a[nx][ny];
                        mx = nx, my = ny;
                    }
                }
            }
        }
    }
    while(q--)
    {
        int x, y, z;
        cin >> x >> y >> z;
        for(int k = 0; k < 13; k++)
        {
            int nx = x + dx[k], ny = y + dy[k];
            if(nx >= 1 && nx <= n && ny >= 1 && ny <= m) 
            {
                a[nx][ny] += z;
                if(a[nx][ny] > maxn)
                {
                    maxn = a[nx][ny];
                    mx = nx, my = ny;
                }
            }
        }
        cout << mx << " " << my << endl;
    }
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int t = 1;
    //cin >> t;
    while (t--)
        solve();
    return 0;
}