本文共 1873 字，大约阅读时间需要 6 分钟。
连接：
意：给出一个800×800下面的矩阵。每次更新一个点的值为以这个点为中心的长度为Li的矩阵内的最大值和最小值的平均值。而且输出这个值。
思路：线段树模板题。二维线段树就是一个树套树的情况。
题的意义就在于给我带了一个二维线段树的模板，跑了2359ms。结构体的线段树不会被卡。
代码：
#include #include #include #include #include #include #include #include #include #include #include #include #include #define PI acos(-1.0)#define maxn 1000#define INF 0x7fffffff#define eps 1e-16#define MOD 1000000009typedef 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() =y2) return query_Max(i<<1,y1,y2); if(yy[i].mid() 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() =x2) return query_Max(i<<1,x1,y1,x2,y2); if(xx[i].mid() >1; change(c_x,c_y,t_need); printf("%d\n",t_need); } } return 0;}
版权声明：本文博客原创文章，博客，未经同意，不得转载。
