朴素 \(O(qn^2)\) 是好想的。转化为对于 \(k\) 和每一个和要求颜色坐标相同的坐标 \((x,y)\)。那么每一次操作相当于对于所有 \((x,y)\)，将 \(p\in[\max(1,x-k),\min(n,i+k)],q\in[\max(1,y-k),\min(n,y+k)]\) 的所有 \((p,q)\) 全部赋值。观察到这是一个矩形。那么我们考虑直接在 \(a\) 上对这个矩形加 \(1\) 或减 \(1\)。多减成了负数或多加成了超过 \(1\) 的就把它们赋成 \(0,1\)。这样操作是等价的。
那么发现很难优化这个 \(n^2\) 部分。我们考虑能否合并 \(q\) 操作使得其被转化成不超过 \(O(n)\) 个等效操作来做到 \(O(n^3)\)。
首先发现，相邻的 \(0\) 或 \(1\) 操作的 \(k\) 可以直接相加。那么我们现在要考虑的操作序列就是形如 \(10101\cdots\) 的了。我们发现，对于一组 \(101\)，如果首尾最小值都大于中间的，那么我们可以直接将其合并成 \(k_1+k_3-k_2\) 的形式。那么这样我们发现新合并的值一定具有单调性。那么又因为如果 \(k>n\) 那么一定直接全 \(0\) 或 \(1\)，这样我们就优化成了 \(O(n^3)\)。
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
using namespace std;
typedef long long ll;
const int MAXN=502;
int n,Q;
struct Query{int op,k;
}q[1000005];
int a[MAXN][MAXN];
namespace Baoli1{vector<vector<int>>b;bool q1,q0;void work(int op,int k){if(q0||q1){return;}vector<vector<int>>sm(n+3);rep(i,0,n+1){sm[i].resize(n+3);}rep(i,1,n){rep(j,1,n){if(b[i][j]==(op==1?1:0)){int upx=max(1,i-k),upy=max(1,j-k);int dnx=min(n,i+k),dny=min(n,j+k);sm[upx][upy]+=op;sm[upx][dny+1]-=op;sm[dnx+1][upy]-=op;sm[dnx+1][dny+1]+=op;}}}q1=true,q0=true;rep(i,1,n){rep(j,1,n){sm[i][j]+=sm[i][j-1]+sm[i-1][j]-sm[i-1][j-1];b[i][j]=min(1,max(0,b[i][j]+sm[i][j]));if(b[i][j]){q0=false;}else{q1=false;}}} }void Do(){q1=q0=false;b.resize(n+2);rep(i,1,n){b[i].resize(n+2);}rep(i,1,n){rep(j,1,n){b[i][j]=a[i][j];}}rep(i,1,Q){work((q[i].op==1?1:-1),q[i].k);}rep(i,1,n){rep(j,1,n){cout<<b[i][j];}cout<<"\n";}}
}
namespace yige1{vector<vector<int>>b;int sjx,sjy,xjx,xjy;bool q1,q0;void work(int op,int k){if(q1||q0){return;}if(op==1){sjx=max(1,sjx-k);sjy=max(1,sjy-k);xjx=min(n,xjx+k);xjy=min(n,xjy+k);if(sjx==1&&sjy==1&&xjx==n&&xjy==n){q1=true;}return;}if(sjx>1){sjx+=k;}if(sjy>1){sjy+=k;}if(xjx<n){xjx-=k;}if(xjy<n){xjy-=k;}if(sjx>n||sjy>n||xjx<0||xjy<0||sjx>xjx||sjy>xjy){q0=true;}}bool check(){int tot=0;rep(i,1,n){rep(j,1,n){tot+=a[i][j];if(tot>1){return false;}}}return tot==1;}void Do(){q1=q0=false;b.resize(n+2);rep(i,1,n){b[i].resize(n+2);}rep(i,1,n){rep(j,1,n){b[i][j]=a[i][j];if(b[i][j]){sjx=xjx=i;sjy=xjy=j;}}}rep(i,1,Q){work(q[i].op,q[i].k);}rep(i,1,n){rep(j,1,n){if(q0){cout<<0;}else if(q1){cout<<1;}else if(sjx<=i&&i<=xjx&&sjy<=j&&j<=xjy){cout<<1;}else{cout<<0;}}cout<<"\n";}}
}
Query sta[1000005];
void Do(int tt){cin>>n>>Q;rep(i,1,n){rep(j,1,n){char c;cin>>c;a[i][j]=c-'0';}}rep(i,1,Q){cin>>q[i].op>>q[i].k;}int tot=0;rep(i,1,Q){if(!tot){sta[++tot]=q[i];}else if(sta[tot].op==q[i].op){sta[tot].k+=q[i].k;}else{sta[++tot]=q[i];}while(tot>2){if(sta[tot-1].k<=min(sta[tot-2].k,sta[tot].k)){sta[tot-2].k+=sta[tot].k-sta[tot-1].k;tot-=2;continue;}break;}}Q=tot;rep(i,1,tot){q[i]=sta[i];}if(yige1::check()){yige1::Do();}else{Baoli1::Do();}
}
int main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T;cin>>T;rep(i,1,T){Do(i);}return 0;
}