连接：http://acm.hdu.edu.cn/showproblem.php?pid=4819
意：给出一个800×800下面的矩阵。每次更新一个点的值为以这个点为中心的长度为Li的矩阵内的最大值和最小值的平均值。而且输出这个值。
思路：线段树模板题。二维线段树就是一个树套树的情况。
题的意义就在于给我带了一个二维线段树的模板，跑了2359ms。结构体的线段树不会被卡。
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <map>
#include <cstdlib>
#include <queue>
#include <stack>
#include <vector>
#include <ctype.h>
#include <algorithm>
#include <string>
#include <set>
#define PI acos(-1.0)
#define maxn 1000
#define INF 0x7fffffff
#define eps 1e-16
#define MOD 1000000009
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
int x_pos[maxn],y_pos[maxn];
int n;//y最大范围
struct y_line
{
int left,right;
int Max,Min;
//int sum;
int mid(){return (left+right)>>1;}
};
struct x_line
{
int left,right;
y_line yy[maxn*4];
int mid(){return (left+right)>>1;}
void build_ytree(int i,int l,int r)
{
yy[i].Max=-INF;
yy[i].Min=INF;
yy[i].left=l;
yy[i].right=r;
if(l==r)
{
y_pos[l]=i;
return ;
}
build_ytree(i<<1,l,yy[i].mid());
build_ytree(i<<1|1,yy[i].mid()+1,r);
}
int query_Min(int i,int y1,int y2)
{
if(yy[i].left==y1&&yy[i].right==y2)
return yy[i].Min;
if(yy[i].mid()>=y2)
return query_Min(i<<1,y1,y2);
if(yy[i].mid()<y1)
return query_Min(i<<1|1,y1,y2);
return min(query_Min(i<<1,y1,yy[i].mid()),query_Min(i<<1|1,yy[i].mid()+1,y2));
}
int query_Max(int i,int y1,int y2)
{
if(yy[i].left==y1&&yy[i].right==y2)
return yy[i].Max;
if(yy[i].mid()>=y2)
return query_Max(i<<1,y1,y2);
if(yy[i].mid()<y1)
return query_Max(i<<1|1,y1,y2);
return max(query_Max(i<<1,y1,yy[i].mid()),query_Max(i<<1|1,yy[i].mid()+1,y2));
}
}xx[maxn*4];
void build_xtree(int i,int l,int r)
{
xx[i].left=l;
xx[i].right=r;
xx[i].build_ytree(1,1,n);
if(l==r)
{
x_pos[l]=i;
return ;
}
build_xtree(i<<1,l,xx[i].mid());
build_xtree(i<<1|1,xx[i].mid()+1,r);
}
void change(int x,int y,int num)
{
int x_p=x_pos[x],y_p=y_pos[y];
for(int i=x_p;i>0;i>>=1)
for(int j=y_p;j>0;j>>=1)
if(j==y_p&&i==x_p)
{
xx[i].yy[j].Max=xx[i].yy[j].Min=num;
}
else if(j==y_p)
{
xx[i].yy[j].Max=max(xx[i<<1].yy[j].Max,xx[i<<1|1].yy[j].Max);
xx[i].yy[j].Min=min(xx[i<<1].yy[j].Min,xx[i<<1|1].yy[j].Min);
}
else
{
xx[i].yy[j].Max=max(xx[i].yy[j<<1].Max,xx[i].yy[j<<1|1].Max);
xx[i].yy[j].Min=min(xx[i].yy[j<<1].Min,xx[i].yy[j<<1|1].Min);
}
}
int query_Min(int i,int x1,int y1,int x2,int y2)
{
if(xx[i].left==x1&&xx[i].right==x2)
return xx[i].query_Min(1,y1,y2);
if(xx[i].mid()>=x2)
return query_Min(i<<1,x1,y1,x2,y2);
if(xx[i].mid()<x1)
return query_Min(i<<1|1,x1,y1,x2,y2);
return min(query_Min(i<<1,x1,y1,xx[i].mid(),y2),query_Min(i<<1|1,xx[i].mid()+1,y1,x2,y2));
}
int query_Max(int i,int x1,int y1,int x2,int y2)
{
if(xx[i].left==x1&&xx[i].right==x2)
return xx[i].query_Max(1,y1,y2);
if(xx[i].mid()>=x2)
return query_Max(i<<1,x1,y1,x2,y2);
if(xx[i].mid()<x1)
return query_Max(i<<1|1,x1,y1,x2,y2);
return max(query_Max(i<<1,x1,y1,xx[i].mid(),y2),query_Max(i<<1|1,xx[i].mid()+1,y1,x2,y2));
}
int main()
{
int T,tot,c_x,c_y,r;
scanf("%d",&T);
for(int ii=1;ii<=T;ii++)
{
scanf("%d",&n);
build_xtree(1,1,n);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
int x;
scanf("%d",&x);
change(i,j,x);
}
scanf("%d",&tot);
printf("Case #%d:
",ii);
for(int i=0;i<tot;i++)
{
scanf("%d%d%d",&c_x,&c_y,&r);
int a,b,c,d;
a=max(1,c_x-r/2);
b=max(1,c_y-r/2);
c=min(n,c_x+r/2);
d=min(n,c_y+r/2);
int t_min=query_Min(1,a,b,c,d);
int t_max=query_Max(1,a,b,c,d);
int t_need=(t_min+t_max)>>1;
change(c_x,c_y,t_need);
printf("%d
",t_need);
}
}
return 0;
}
版权声明：本文博客原创文章，博客，未经同意，不得转载。