题目大意:给你一个ｎ＊ｎ的矩阵，每次找到一个点(x,y)周围ｌ＊ｌ的子矩阵中的最大值ａ和最小值ｂ，将(x,y)更新为(a+b)/2
思路:裸的二维线段树
#include<iostream>
#include<cstdio>#include <math.h>#include<algorithm>#include<string.h>#include<queue>#define MOD 10000007#define maxn 3500#define LL long longusing namespace std;int tree_max[maxn][maxn],tree_min[maxn][maxn],ans_min,ans_max,n;int a[maxn][maxn];void build_y(int xx,int node,int l,int r,int x,int type){ if(l+1==r){ if(type)tree_max[xx][node]=tree_min[xx][node]=a[x][l]; else { tree_max[xx][node]=max(tree_max[xx*2][node],tree_max[xx*2+1][node]); tree_min[xx][node]=min(tree_min[xx*2][node],tree_min[xx*2+1][node]); } return ; } int mid=(l+r)>>1; build_y(xx,node*2,l,mid,x,type); build_y(xx,node*2+1,mid,r,x,type); tree_max[xx][node]=max(tree_max[xx][node*2],tree_max[xx][node*2+1]); tree_min[xx][node]=min(tree_min[xx][node*2],tree_min[xx][node*2+1]);}void build_x(int node,int l,int r){ if(l+1==r) { build_y(node,1,1,n+1,l,1); return ; } int mid=(l+r)>>1; build_x(node*2,l,mid); build_x(node*2+1,mid,r); build_y(node,1,1,n+1,l,0);}void query_y(int xx,int node,int l,int r,int ql,int qr){ if(ql<=l&&r<=qr) { ans_max=max(ans_max,tree_max[xx][node]); ans_min=min(ans_min,tree_min[xx][node]); return; } int mid=(l+r)>>1; if(ql<mid)query_y(xx,node*2,l,mid,ql,qr); if(qr>mid)query_y(xx,node*2+1,mid,r,ql,qr);}void query_x(int node,int l,int r,int ql,int qr,int y1,int y2){ if(ql<=l && r<=qr) { query_y(node,1,1,1+n,y1,y2);return ; } int mid=(l+r)>>1; if(ql<mid)query_x(node*2,l,mid,ql,qr,y1,y2); if(qr>mid)query_x(node*2+1,mid,r,ql,qr,y1,y2);}void update_y(int xx,int node,int l,int r,int pos,int num,int type){ if(l+1==r){ if(type)tree_max[xx][node]=tree_min[xx][node]=num; else{ tree_max[xx][node]=max(tree_max[xx*2][node],tree_max[xx*2+1][node]); tree_min[xx][node]=min(tree_min[xx*2][node],tree_min[xx*2+1][node]); } return ; } int mid=(l+r)>>1; if(pos<mid)update_y(xx,node*2,l,mid,pos,num,type);else update_y(xx,node*2+1,mid,r,pos,num,type); tree_max[xx][node]=max(tree_max[xx][node*2],tree_max[xx][node*2+1]); tree_min[xx][node]=min(tree_min[xx][node*2],tree_min[xx][node*2+1]);}void update_x(int node,int l,int r,int x,int y,int num){ if(l+1==r) { update_y(node,1,1,n+1,y,num,1); return ; } int mid=(l+r)>>1; if(x<mid)update_x(node*2,l,mid,x,y,num); else update_x(node*2+1,mid,r,x,y,num); update_y(node,1,1,n+1,y,num,0);}int main(){ int t,cas=0; scanf("%d",&t); while(t--) { memset(tree_max,0,sizeof(tree_max)); memset(tree_min,0,sizeof(tree_min)); printf("Case #%d:\n",++cas); int q,x,y,l; scanf("%d",&n); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++)scanf("%d",&a[i][j]); build_x(1,1,n+1); scanf("%d",&q); while(q--) { scanf("%d%d%d",&x,&y,&l);l=(l-1)>>1; ans_max=0;ans_min=0x3f3f3f3f; query_x(1,1,n+1,max(x-l,1),min(x+l+1,n+1),max(y-l,1),min(y+l+1,n+1)); update_x(1,1,n+1,x,y,(ans_max+ans_min)>>1); printf("%d\n",(ans_max+ans_min)>>1); } } return 0;}