HDU 4819 Mosaic D区段树

连接：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:\n",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\n",t_need);
        }
    }
    return 0;
}