题意：
给出一个n*n的矩阵，给出矩阵中所有位置的值
给出m个询问
对于每个询问有x,y,l，分表表示坐标与以该坐标为中心的正方形
对于每组查询我们输出该正方形中的最大值跟最小值的和除2向下取整，再用这个值取代原来在(x,y)的值
solve：
明显是二维线段树模板题 ，分别维护x跟y就行了，对于每个点建一棵线段树
#include <bits/stdc++.h> using namespace std; #define ll long long #define re register void read(int &a) { a=0;int d=1;char ch; while(ch=getchar(),ch>'9'||ch<'0') if(ch=='-') d=-1; a=ch^48; while(ch=getchar(),ch>='0'&&ch<='9') a=(a<<3)+(a<<1)+(ch^48); a*=d; } int minn[3205][3205],maxx[3205][3205]; int n,minnn,maxxx; void pushupx1(int l,int r,int nowx,int nowy) { minn[nowx][nowy]=min(minn[nowx<<1][nowy],minn[nowx<<1|1][nowy]); maxx[nowx][nowy]=max(maxx[nowx<<1][nowy],maxx[nowx<<1|1][nowy]); if(l==r) return; int m=l+r>>1; pushupx1(l,m,nowx,nowy<<1),pushupx1(m+1,r,nowx,nowy<<1|1); } void pushupx11(int y,int l,int r,int nowx,int nowy) { minn[nowx][nowy]=min(minn[nowx<<1][nowy],minn[nowx<<1|1][nowy]); maxx[nowx][nowy]=max(maxx[nowx<<1][nowy],maxx[nowx<<1|1][nowy]); if(l==r) return; int m=l+r>>1; if(m>=y) pushupx11(y,l,m,nowx,nowy<<1); else pushupx11(y,m+1,r,nowx,nowy<<1|1); } void buildy(int l,int r,int nowx,int nowy) { if(l==r) { int x;read(x); minn[nowx][nowy]=maxx[nowx][nowy]=x; return; } int m=l+r>>1; buildy(l,m,nowx,nowy<<1),buildy(m+1,r,nowx,nowy<<1|1); minn[nowx][nowy]=min(minn[nowx][nowy<<1],minn[nowx][nowy<<1|1]); maxx[nowx][nowy]=max(maxx[nowx][nowy<<1],maxx[nowx][nowy<<1|1]); } void buildx(int l,int r,int nowx) { if(l==r) { buildy(1,n,nowx,1); return; } int m=l+r>>1; buildx(l,m,nowx<<1),buildx(m+1,r,nowx<<1|1); pushupx1(1,n,nowx,1); } void queryy(int yl,int yr,int l,int r,int nowx,int nowy) { if(l>=yl&&r<=yr) { minnn=min(minn[nowx][nowy],minnn); maxxx=max(maxx[nowx][nowy],maxxx); return; } int m=l+r>>1; if(m>=yl) queryy(yl,yr,l,m,nowx,nowy<<1); if(m<yr) queryy(yl,yr,m+1,r,nowx,nowy<<1|1); } void queryx(int xl,int xr,int yl,int yr,int l,int r,int nowx) { if(l>=xl&&r<=xr) { queryy(yl,yr,1,n,nowx,1); return; } int m=l+r>>1; if(m>=xl) queryx(xl,xr,yl,yr,l,m,nowx<<1); if(m<xr) queryx(xl,xr,yl,yr,m+1,r,nowx<<1|1); } void updatey(int y,int val,int l,int r,int nowx,int nowy) { if(l==y&&r==y) { minn[nowx][nowy]=maxx[nowx][nowy]=val; return; } int m=l+r>>1; if(m>=y) updatey(y,val,l,m,nowx,nowy<<1); else updatey(y,val,m+1,r,nowx,nowy<<1|1); minn[nowx][nowy]=min(minn[nowx][nowy<<1],minn[nowx][nowy<<1|1]); maxx[nowx][nowy]=max(maxx[nowx][nowy<<1],maxx[nowx][nowy<<1|1]); } void updatex(int x,int y,int val,int l,int r,int nowx) { if(l==x&&r==x) { updatey(y,val,1,n,nowx,1); return; } int m=l+r>>1; if(m>=x) updatex(x,y,val,l,m,nowx<<1); else updatex(x,y,val,m+1,r,nowx<<1|1); pushupx11(y,1,n,nowx,1); } int main() { int T,cas=1; read(T); while(T--) { read(n); for(re int i=1;i<=n<<2;i++) { for(re int j=1;j<=n<<2;j++) { minn[i][j]=0x3fffffff; maxx[i][j]=-0x3fffffff; } } buildx(1,n,1); int m;read(m); printf("Case #%d: ",cas++); while(m--) { int x,y,l; read(x),read(y),read(l); minnn=0x3fffffff,maxxx=-0x3fffffff; queryx(max(1,x-l/2),min(n,x+l/2),max(1,y-l/2),min(n,y+l/2),1,n,1); int val=(minnn+maxxx)/2; updatex(x,y,val,1,n,1); printf("%d ",val); } } return 0; }