http://acm.hdu.edu.cn/showproblem.php?pid=4819
给出一个N*N的矩阵，每次询问一个m*m的子矩阵里的floor((maxv+minv)/2)并把中间的元素修改为这个值。
线段树套线段树，第一层X表示对行建立的线段树，内层表示对Y也就是列建立的线段树。
分别对X和Y建立相应的函数来完成操作，当更新X树的节点时，再更新完当前X的节点的左右儿子之后，回头对X的这个节点对应的Y树进行更新，相当于X的左右儿子里的Y树来更新X的Y树，能理解这一点就很简单了。
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define mp make_pair
#define LL long long
#define lc (id<<1)
#define rc (id<<1|1)
#define flc (fid<<1)
#define frc (fid<<1|1)
#define mid ((L+R)>>1)
const int maxn=;
int maxv[maxn<<][maxn<<];
int minv[maxn<<][maxn<<];
int a[maxn][maxn],N,x1,x2,y1,y2;
void buildY(int,int,int,int,int,int);
void buildX(int id,int L,int R){
if(L==R){
buildY(id,L,R,,,N);
}
else{
buildX(lc,L,mid);
buildX(rc,mid+,R);
buildY(id,L,R,,,N);
}
}
void buildY(int fid,int fl,int fr,int id,int L,int R){
if(L==R){
if(fl==fr)maxv[fid][id]=minv[fid][id]=a[fl][L];
else{
maxv[fid][id]=max(maxv[flc][id],maxv[frc][id]);
minv[fid][id]=min(minv[flc][id],minv[frc][id]);
}
}
else{
buildY(fid,fl,fr,lc,L,mid);
buildY(fid,fl,fr,rc,mid+,R);
maxv[fid][id]=max(maxv[fid][lc],maxv[fid][rc]);
minv[fid][id]=min(minv[fid][lc],minv[fid][rc]);
}
}
pii askY(int fid,int id,int L,int R){
if(L>=y1&&R<=y2){
return mp(maxv[fid][id],minv[fid][id]);
}
else{
if(y2<=mid) return askY(fid,lc,L,mid);
else if(y1>mid) return askY(fid,rc,mid+,R);
else{
pii pl=askY(fid,lc,L,mid),
pr=askY(fid,rc,mid+,R);
return mp(max(pl.first,pr.first),min(pl.second,pr.second));
}
}
}
pii askX(int id,int L,int R){
if(L>=x1&&R<=x2){
return askY(id,,,N);
}
else{
if(x2<=mid) return askX(lc,L,mid);
else if(x1>mid) return askX(rc,mid+,R);
else{
pii pl=askX(lc,L,mid),
pr=askX(rc,mid+,R);
return mp(max(pl.first,pr.first),min(pl.second,pr.second));
}
}
}
void updateY(int fid,int fl,int fr,int id,int L,int R,int x,int y,int v){
if(L==R){
if(fl==fr){
maxv[fid][id]=minv[fid][id]=v;
}
else{
maxv[fid][id]=max(maxv[flc][id],maxv[frc][id]);
minv[fid][id]=min(minv[flc][id],minv[frc][id]);
}
}
else{
if(y<=mid){
updateY(fid,fl,fr,lc,L,mid,x,y,v);
}
else{
updateY(fid,fl,fr,rc,mid+,R,x,y,v);
}
maxv[fid][id]=max(maxv[fid][lc],maxv[fid][rc]);
minv[fid][id]=min(minv[fid][lc],minv[fid][rc]);
}
}
void updateX(int id,int L,int R,int x,int y,int v){
if(L==R){
updateY(id,L,R,,,N,x,y,v);
}
else{
if(x<=mid) updateX(lc,L,mid,x,y,v);
else updateX(rc,mid+,R,x,y,v);
updateY(id,L,R,,,N,x,y,v);
}
}
int main()
{
int T,M,i,j,x,y,d;
scanf("%d",&T);
for(int cas=;cas<=T;++cas){
scanf("%d",&N);
for(i=;i<=N;++i){
for(j=;j<=N;++j){
scanf("%d",&a[i][j]);
}
}
buildX(,,N);
scanf("%d",&M);
printf("Case #%d:\n",cas);
while(M--){
scanf("%d%d%d",&x,&y,&d);
x1=x-d/,x2=x+d/,y1=y-d/,y2=y+d/;
x1=max(x1,),x2=min(x2,N);
y1=max(y1,),y2=min(y2,N);
pii ans=askX(,,N);
updateX(,,N,x,y,(ans.first+ans.second)/);
printf("%d\n",(ans.first+ans.second)/);
}
}
return ;
}