按照题意模拟即可。
核心就是维护这个网格，每次修改之后只更新所有包含该点的 \(k\times k\) 子矩阵的元素和，并维护其最大值。
由于题目保证每次修改都是增加正整数，因此子矩阵和单调不减，最大值也只会变大，直接更新即可。
虽然说时间复杂度不是很优秀但是对于本题已经足够，时间复杂度是 \(O(q\times k^2)\)。
本质上就是每次修改后局部更新，这样就保证不会炸掉。
aclink。
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define uint unsigned int
#define i128 __int128
#define ld long double
#define fir first
#define sec second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
#define lowbit(x) (x&-x)
using namespace std;
const int MOD=998244353;
const int MOD1=1e9+7;
//char ibuf[1<<25],*p1=buf,*p2=buf;
mt19937 mrand(random_device{}());
int rnd(int x){ return mrand() % x;}
ll qpow(ll a,ll b){ll res=1;while(b){if(b&1)res=res*a%MOD;a=a*a%MOD,b>>=1;}return res;}
ll gcd(ll a,ll b){ return b?gcd(b,a%b):a;}
//C++ 17 -O2
//By MaZhaoze
int main(){int n,k;cin>>n>>k;int g[n+1][n+1]={0};int s[n-k+2][n-k+2]={0};int q;int now=0;cin>>q;while(q--){int r,c,v;cin>>r>>c>>v;int temp=v-g[r][c];g[r][c]=v;int is = max(1,r-k+1);int ie = min(r,n-k+1);int js = max(1,c-k+1);int je = min(c,n-k+1);for(int i=is;i<=ie;i++){for(int j=js;j<=je;j++){s[i][j]+=temp;now=max(now,s[i][j]);}}cout<<now<<'\n';}return 0;
}
考虑如何更优。
更优做法可将每次修改转化为对子矩阵和矩阵 \(S\) 的矩形区间加上一个全局最大值查询。按行拆分矩形更新，用线段树维护区间加与最大值，从 \(O(qk^2)\) 优化到 \(O(qk\log n)\)。如果本题的 \(k\) 在拉高一点，这个做法就相当有优势了。
但是说实话，这题 \(k \le 25\)，暴力已冲过去了，线段树上来常数更大还更容易写炸，直接用暴力就够了。
aclink。
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define uint unsigned int
#define i128 __int128
#define ld long double
#define fir first
#define sec second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
#define lowbit(x) (x&-x)
using namespace std;
const int MOD=998244353;
const int MOD1=1e9+7;
//char ibuf[1<<25],*p1=buf,*p2=buf;
mt19937 mrand(random_device{}());
int rnd(int x){ return mrand() % x;}
ll qpow(ll a,ll b){ll res=1;while(b){if(b&1)res=res*a%MOD;a=a*a%MOD,b>>=1;}return res;}
ll gcd(ll a,ll b){ return b?gcd(b,a%b):a;}
//C++ 17 -O2
//By MaZhaoze
struct SegTree {int n;vector<long long> mx, lazy;SegTree() {}SegTree(int _n) { init(_n); }void init(int _n) {n = _n;mx.assign(4 * n + 5, 0);lazy.assign(4 * n + 5, 0);}void push(int p) {if (lazy[p] != 0) {long long v = lazy[p];mx[p << 1] += v;mx[p << 1 | 1] += v;lazy[p << 1] += v;lazy[p << 1 | 1] += v;lazy[p] = 0;}}void range_add(int p, int l, int r, int ql, int qr, long long val) {if (ql <= l && r <= qr) {mx[p] += val;lazy[p] += val;return;}push(p);int mid = (l + r) >> 1;if (ql <= mid) range_add(p << 1, l, mid, ql, qr, val);if (qr > mid) range_add(p << 1 | 1, mid + 1, r, ql, qr, val);mx[p] = max(mx[p << 1], mx[p << 1 | 1]);}void add(int l, int r, long long val) {if (l > r) return;range_add(1, 1, n, l, r, val);}long long getMax() const {return mx[1];}
};int main(){int N, K;cin >> N >> K;int Q;cin >> Q;int m = N - K + 1; vector<vector<int>> g(N + 1, vector<int>(N + 1, 0)); vector<SegTree> seg(m + 1);for (int i = 1; i <= m; i++) seg[i].init(m);multiset<long long> rowMax;for (int i = 1; i <= m; i++) rowMax.insert(0);while (Q--) {int r, c, v;cin >> r >> c >> v;int delta = v - g[r][c];g[r][c] = v;int is = max(1, r - K + 1);int ie = min(r, m);int js = max(1, c - K + 1);int je = min(c, m);for (int i = is; i <= ie; i++) {long long oldMax = seg[i].getMax();auto it = rowMax.find(oldMax);rowMax.erase(it);seg[i].add(js, je, delta);long long newMax = seg[i].getMax();rowMax.insert(newMax);}cout << *rowMax.rbegin() << "\n";}return 0;
}