hdu 4819 Mosaic (二維線段樹)

其實後來看了題解以後知道 更新一維可以直接在建立二維的時候就完成。再加入就是多此一舉了。

其中的pushupy是多余的。。。

#include 
#include 
#include 
#include 
#define maxn 805
#define inf 0x3f3f3f3f
using namespace std;

int Min[maxn*3][maxn*3];
int Max[maxn*3][maxn*3];
int ansmin,ansmax;
int n;
inline int ReadInt()
{
    char ch = getchar();
    int data = 0;
    while (ch < '0' || ch > '9')
    {
        ch = getchar();
    }
    do
    {
        data = data*10 + ch-'0';
        ch = getchar();
    }while (ch >= '0' && ch <= '9');
        return data;
}

inline void pushupx(int pos,int num)
{
    Min[pos][num]=Min[pos][num<<1]>Min[pos][num<<1|1]?Min[pos][num<<1|1]:Min[pos][num<<1];
    Max[pos][num]=Max[pos][num<<1]>Max[pos][num<<1|1]?Max[pos][num<<1]:Max[pos][num<<1|1];
}

inline void pushupy(int pos,int num,int s,int e)
{
    Min[pos][num]=Min[pos<<1][num]Max[pos<<1|1][num]?Max[pos<<1][num]:Max[pos<<1|1][num];
    if(s==e)
        return;
    int mid=(s+e)>>1;
    pushupy(pos,num<<1,s,mid);
    pushupy(pos,num<<1|1,mid+1,e);
}

void buildx(int pos,int num,int s,int e,int rt)
{
    if(s==e)
    {
        if(rt==-1){
            int a;
            a=ReadInt();
            Max[pos][num]=Min[pos][num]=a;
        }
        else
        {
            Min[pos][num]=min(Min[pos<<1][num],Min[pos<<1|1][num]);
            Max[pos][num]=max(Max[pos<<1][num],Max[pos<<1|1][num]);
        }
        return;
    }
    int mid=(s+e)>>1;
    buildx(pos,num<<1,s,mid,rt);
    buildx(pos,num<<1|1,mid+1,e,rt);
    pushupx(pos,num);
}
void buildy(int num,int s,int e)
{
    if(s==e)
    {
        buildx(num,1,1,n,-1);
        return;
    }
    int mid=(s+e)>>1;
    buildy(num<<1,s,mid);
    buildy(num<<1|1,mid+1,e);

    buildx(num,1,1,n,1);
}

void queryx(int pos,int num,int s,int e,int l,int r)
{
    if(l<=s && r>=e)
    {
        ansmin=Min[pos][num]ansmax?Max[pos][num]:ansmax;
        return ;
    }
    int mid=(s+e)>>1;
    if(r<=mid)queryx(pos,num<<1,s,mid,l,r);
    else if(l>mid)queryx(pos,num<<1|1,mid+1,e,l,r);
    else
    {
        queryx(pos,num<<1,s,mid,l,mid);
        queryx(pos,num<<1|1,mid+1,e,mid+1,r);
    }
}
void queryy(int num,int s,int e,int l,int r,int u,int d)
{
    if(l<=s && r>=e)
    {
        queryx(num,1,1,n,u,d);
        return;
    }
    int mid=(s+e)>>1;
    if(r<=mid)queryy(num<<1,s,mid,l,r,u,d);
    else if(l>mid)queryy(num<<1|1,mid+1,e,l,r,u,d);
    else
    {
        queryy(num<<1,s,mid,l,mid,u,d);
        queryy(num<<1|1,mid+1,e,mid+1,r,u,d);
    }
}
void updatex(int pos,int num,int s,int e,int p,int val,int rt)
{
    if(s==e)
    {
        if(rt!=-1){
            Min[pos][num]=Max[pos][num]=val;
        }
        else
        {
            Min[pos][num]=min(Min[pos<<1][num],Min[pos<<1|1][num]);
            Max[pos][num]=max(Max[pos<<1][num],Max[pos<<1|1][num]);
        }
        return;
    }
    int mid=(s+e)>>1;
    if(p<=mid)updatex(pos,num<<1,s,mid,p,val,rt);
    else updatex(pos,num<<1|1,mid+1,e,p,val,rt);
    pushupx(pos,num);
}

void updatey(int num,int s,int e,int posy,int posx,int val)
{

    if(s==e)
    {
        updatex(num,1,1,n,posx,val,1);
        return;
    }
    int mid=(s+e)>>1;
    if(posy<=mid)updatey(num<<1,s,mid,posy,posx,val);
    else updatey(num<<1|1,mid+1,e,posy,posx,val);

    updatex(num,1,1,n,posx,val,-1);
}

int main()
{
    int T;

    T=ReadInt();

    for(int cas=1;cas<=T;cas++)
    {
        printf(Case #%d:
,cas);
        n=ReadInt();

        buildy(1,1,n);
        int m;
        m=ReadInt();

        while(m--)
        {

            int r,l,siz;
            r=ReadInt();
            l=ReadInt();
            siz=ReadInt();

            siz/=2;

            int up,down,left,right;

            up=1>r-siz?1:r-siz;
            down=nl-siz?1:l-siz;
            right=ndown)
                swap(up,down);
            if(left>right)
                swap(left,right);

            ansmin=inf;
            ansmax=-1;

            queryy(1,1,n,up,down,left,right);

            updatey(1,1,n,r,l,(ansmin+ansmax)/2);

            printf(%d
,(ansmin+ansmax)/2);
        }
    }
    return 0;
}