思路：
二维线段树模板题，马克一下，以后当模板用
代码：
#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
const int N = 1024+5;
int MAX[N<<2][N<<2],MIN[N<<2][N<<2],n,minv,maxv;
void push_upx(int deep,int rt){
MAX[deep][rt] = max(MAX[deep<<1][rt],MAX[deep<<1|1][rt]);
MIN[deep][rt] = min(MIN[deep<<1][rt],MIN[deep<<1|1][rt]);
}
void push_upy(int deep,int rt){
MAX[deep][rt] = max(MAX[deep][rt<<1],MAX[deep][rt<<1|1]);
MIN[deep][rt] = min(MIN[deep][rt<<1],MIN[deep][rt<<1|1]);
}
void buildy(int ly,int ry,int deep,int rt,int flag){
//y轴范围ly,ry;deep,rt;标记flag
if(ly == ry){
if(flag){
int tmp;
scanf("%d",&tmp);
MAX[deep][rt] = MIN[deep][rt] = tmp;
}
else push_upx(deep,rt);
return;
}
int m = (ly + ry) >> 1;
buildy(ly,m,deep,rt << 1,flag);
buildy(m+1,ry,deep,rt << 1 | 1,flag);
push_upy(deep,rt);
}
void buildx(int lx,int rx,int deep){
//建树x轴范围lx,rx;deep
if(lx == rx){
buildy(1,n,deep,1,1);
return;
}
int m = (lx + rx) >> 1;
buildx(lx,m,deep << 1);
buildx(m+1,rx,deep << 1 | 1);
buildy(1,n,deep,1,0);
}
void updatey(int Y,int val,int ly,int ry,int deep,int rt,int flag){
//单点更新y坐标;更新值val;当前操作y的范围ly,ry;deep,rt;标记flag
if(ly == ry){
if(flag) MAX[deep][rt] = MIN[deep][rt] = val;
else push_upx(deep,rt);
return;
}
int m = (ly + ry) >> 1;
if(Y <= m) updatey(Y,val,ly,m,deep,rt << 1,flag);
else updatey(Y,val,m + 1,ry,deep,rt << 1 | 1,flag);
push_upy(deep,rt);
}
void updatex(int X,int Y,int val,int lx,int rx,int deep){
//单点更新范围x,y;更新值val;当前操作x的范围lx,rx;deep
if(lx == rx){
updatey(Y,val,1,n,deep,1,1);
return;
}
int m = (lx + rx) >> 1;
if(X <= m) updatex(X,Y,val,lx,m,deep << 1);
else updatex(X,Y,val,m + 1,rx,deep << 1 | 1);
updatey(Y,val,1,n,deep,1,0);
}
void queryy(int Yl,int Yr,int ly,int ry,int deep,int rt){
//询问区间y轴范围y1,y2;当前操作y的范围ly,ry;deep,rt
if(Yl <= ly && ry <= Yr){
minv = min(MIN[deep][rt],minv);
maxv = max(MAX[deep][rt],maxv);
return;
}
int m = (ly + ry) >> 1;
if(Yl <= m)
queryy(Yl,Yr,ly,m,deep,rt << 1);
if(m < Yr)
queryy(Yl,Yr,m + 1,ry,deep,rt << 1 | 1);
}
void queryx(int Xl,int Xr,int Yl,int Yr,int lx,int rx,int rt){
//询问区间范围x1,x2,y1,y2;当前操作x的范围lx,rx;rt
if(Xl <= lx && rx <= Xr){
queryy(Yl,Yr,1,n,rt,1);
return;
}
int m = (lx + rx) >> 1;
if(Xl <= m)
queryx(Xl,Xr,Yl,Yr,lx,m,rt << 1);
if(m < Xr)
queryx(Xl,Xr,Yl,Yr,m + 1,rx,rt << 1 | 1);
}
int main(){
int T,Case = 1;
scanf("%d",&T);
while(T--){
//memset(MAX,-1,sizeof(MAX));
//memset(MIN,63,sizeof(MIN));
scanf("%d",&n);
buildx(1,n,1);
int q,X,Y,r,odd,x1,x2,y1,y2;
scanf("%d",&q);
printf("Case #%d:\n",Case++);
while(q--){
maxv = -1,minv = 1000000005;
scanf("%d%d%d",&X,&Y,&odd);
r = odd >> 1;
x1 = max(X - r,1); //注意一下范围
y1 = max(Y - r,1);
x2 = min(X + r,n);
y2 = min(Y + r,n);
queryx(x1,x2,y1,y2,1,n,1);
int ans = (maxv + minv) >> 1;
printf("%d\n",ans);
updatex(X,Y,ans,1,n,1);
}
}
return 0;
}