题目链接：6709 Mosaic
题解：参考这个博客:二维线段树，先按行建树然后每一个节点也是一个棵线段树按列建。
#include<bits/stdc++.h>
#include<cmath>
#include<set>
#include<cstdio>
#include<iomanip>
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#define pb push_back
#define mk make_pair
#define fi first
#define se second
#define ll long long
#define PI 3.14159265
#define ls l,m,rt<<1
#define rs m+1,r,rt<<1|1
#define eps 1e-7
using namespace std;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef pair<int,int>pii;
const int mod=1e9+9;
const int INF=0x4f4f4f4f;
const int base=13331;
const ll inf=1e18+100;
const int maxn=800;
int n,m,cnt,num[maxn+5][maxn+5],t;
struct segmentxy
{
int MIN[(maxn<<2)+5][(maxn<<2)+5],MAX[(maxn<<2)+5][(maxn<<2)+5],lx,rx,ly,ry,fa,is_leaf,px,py,val;//fa是当前x树的根，is判断是否为叶节点的树
void pushupx(int fa,int p)//更新行
{
MIN[fa][p]=min(MIN[fa<<1][p],MIN[fa<<1|1][p]);
MAX[fa][p]=max(MAX[fa<<1][p],MAX[fa<<1|1][p]);
}
void pushupy(int fa,int p)//更新列
{
MIN[fa][p]=min(MIN[fa][p<<1],MIN[fa][p<<1|1]);
MAX[fa][p]=max(MAX[fa][p<<1],MAX[fa][p<<1|1]);
}
void buildy(int l,int r,int rt,int *a)
{
if(l==r){if(is_leaf)MAX[fa][rt]=MIN[fa][rt]=a[l];else pushupx(fa,rt);return;}
int m=(l+r)>>1;
buildy(ls,a);buildy(rs,a);
pushupy(fa,rt);
}
void buildx(int l,int r,int rt)
{
if(l==r){is_leaf=true;fa=rt;buildy(ly,ry,1,num[l]);}
else
{
int m=(l+r)>>1;
buildx(ls);buildx(rs);
fa=rt;is_leaf=false;buildy(ly,ry,1,num[l]);
}
}
void build(int xl,int xr,int yl,int yr)
{
lx=xl;rx=xr;ly=yl;ry=yr;
buildx(lx,rx,1);
}
void updatey(int l,int r,int rt)
{
if(l==r){if(is_leaf)MAX[fa][rt]=MIN[fa][rt]=val;else pushupx(fa,rt);return;}
{
int m=(l+r)>>1;
if(py<=m)updatey(ls);
else updatey(rs);
pushupy(fa,rt);
}
}
void updatex(int l,int r,int rt)
{
if(l==r){is_leaf=true;fa=rt;updatey(1,n,1);return;}
else
{
int m=(l+r)>>1;
if(px<=m)updatex(ls);
else updatex(rs);
is_leaf=false;fa=rt;updatey(1,n,1);
}
}
void update(int x,int y,int z)
{
px=x;py=y;val=z;updatex(1,n,1);
}
int querymax_y(int l,int r,int rt)
{
if(ly<=l&&r<=ry){return MAX[fa][rt];}
else
{
int m=(l+r)>>1,ans=0;
if(ly<=m)ans=max(ans,querymax_y(ls));
if(ry>m)ans=max(ans,querymax_y(rs));
return ans;
}
}
int querymax_x(int l,int r,int rt)
{
if(lx<=l&&r<=rx){fa=rt;return querymax_y(1,n,1);}
else
{
int ans=0;int m=(l+r)>>1;fa=rt;
if(lx<=m)ans=max(ans,querymax_x(ls));
if(rx>m) ans=max(ans,querymax_x(rs));
return ans;
}
}
int querymin_y(int l,int r,int rt)
{
if(ly<=l&&r<=ry){return MIN[fa][rt];}
else
{
int m=(l+r)>>1,ans=INF;
if(ly<=m)ans=min(ans,querymin_y(ls));
if(ry>m)ans=min(ans,querymin_y(rs));
return ans;
}
}
int querymin_x(int l,int r,int rt)
{
if(lx<=l&&r<=rx){fa=rt;return querymin_y(1,n,1);}
else
{
int ans=INF;int m=(l+r)>>1;fa=rt;
if(lx<=m)ans=min(ans,querymin_x(ls));
if(rx>m)ans=min(ans,querymin_x(rs));
return ans;
}
}
int query(int xl,int xr,int yl,int yr)
{
lx=xl;rx=xr;ly=yl;ry=yr;
int an1=querymax_x(1,n,1);
int an2=querymin_x(1,n,1);
return (an1+an2)>>1;
}
}tr;
int main()
{
scanf("%d",&t);
for(int cas=1;cas<=t;cas++)
{
printf("Case #%d:
",cas);
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
scanf("%d",&num[i][j]);
}
}
tr.build(1,n,1,n);
scanf("%d",&m);
while(m--)
{
int lx,rx,ly,ry,x,y,z;
scanf("%d %d %d",&x,&y,&z);z/=2;
lx=max(0,x-z);rx=min(n,x+z);
ly=max(0,y-z);ry=min(n,y+z);
int ans=tr.query(lx,rx,ly,ry);
printf("%d
",ans);
tr.update(x,y,ans);
}
}
return 0;
}