HDU 4819 Mosaic（二维线段树单点更新+区间查询+自己的写法模板）

ゞ浴缸里的玫瑰 2022-06-10 08:39 160阅读 0赞

The God of sheep decides to pixelate some pictures (i.e., change them into pictures with mosaic). Here's how he is gonna make it: for each picture, he divides the picture into n x n cells, where each cell is assigned a color value. Then he chooses a cell, and checks the color values in the L x L region whose center is at this specific cell. Assuming the maximum and minimum color values in the region is A and B respectively, he will replace the color value in the chosen cell with floor((A + B) / 2).  
  
Can you help the God of sheep?

Input

The first line contains an integer T (T ≤ 5) indicating the number of test cases. Then T test cases follow.  
  
Each test case begins with an integer n (5 < n < 800). Then the following n rows describe the picture to pixelate, where each row has n integers representing the original color values. The j-th integer in the i-th row is the color value of cell (i, j) of the picture. Color values are nonnegative integers and will not exceed 1,000,000,000 (10^9).  
  
After the description of the picture, there is an integer Q (Q ≤ 100000 (10^5)), indicating the number of mosaics.  
  
Then Q actions follow: the i-th row gives the i-th replacement made by the God of sheep: xi, yi, Li (1 ≤ xi, yi ≤ n, 1 ≤ Li < 10000, Li is odd). This means the God of sheep will change the color value in (xi, yi) (located at row xi and column yi) according to the Li x Li region as described above. For example, an query (2, 3, 3) means changing the color value of the cell at the second row and the third column according to region (1, 2) (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 2), (3, 3), (3, 4). Notice that if the region is not entirely inside the picture, only cells that are both in the region and the picture are considered.  
  
Note that the God of sheep will do the replacement one by one in the order given in the input.��

Output

For each test case, print a line "Case \#t:"(without quotes, t means the index of the test case) at the beginning.  
  
For each action, print the new color value of the updated cell.

Sample Input

1
    3
    1 2 3
    4 5 6
    7 8 9
    5
    2 2 1
    3 2 3
    1 1 3
    1 2 3
    2 2 3

Sample Output

Case #1:
    5
    6
    3
    4
    6

题解：

这题我之前的博客上有题解，今天又做了一题二维线段树的题，感觉比这题简单一些：[http://blog.csdn.net/qq\_37497322/article/details/77165175][http_blog.csdn.net_qq_37497322_article_details_77165175]

然后因为之前我这一题是直接看别人的博客似懂非懂，今天昨晚那题感觉悟道了些什么再重新自己做一遍。。如果要详解看我之前的博客有：[http://blog.csdn.net/qq\_37497322/article/details/77094852][http_blog.csdn.net_qq_37497322_article_details_77094852]，这里贴上我自己的代码：

#include <iostream>
    #include <stdio.h>
    #include <cstring>
    #include<math.h>
    #include<string>
    #include<stack>
    #include<queue>
    #include<list>
    #include<vector>
    #include <algorithm>
    using namespace std;
    #define INF 1008611111//这个要大一点不然WA
    #define lson k*2
    #define rson k*2+1
    #define M (l+r)/2
    int maxn[801*3][801*3];//这里测试数据不大可以开3倍
    int minn[801*3][801*3];
    int que1,que2;//存询问的最大最小值
    int L1,L2,R1,R2;//存询问的一维二维区间
    int n,tag;//tag是是否找到了一维下标
    void update1(int fk,int l,int r,int pos,int k,int v)//更新二维，pos为二维位置，fk为父节点此时的下标
    {
        if(l==r)//如果找到了二维下标
        {
            if(tag)//如果此时正好找到了一维下标，就赋值
            {
                tag=0;//记得要清零
                maxn[fk][k]=v;
                minn[fk][k]=v;
            }
            else//否则更新一维的情况
            {
                maxn[fk][k]=max(maxn[fk*2][k],maxn[fk*2+1][k]);
                minn[fk][k]=min(minn[fk*2][k],minn[fk*2+1][k]);
            }
            return;
        }
        int mid=M;
        if(pos<=mid)
            update1(fk,l,mid,pos,lson,v);
        else
            update1(fk,mid+1,r,pos,rson,v);
        maxn[fk][k]=max(maxn[fk][lson],maxn[fk][rson]);//递归回来更新二维情况
        minn[fk][k]=min(minn[fk][lson],minn[fk][rson]);
    }
    void update2(int k,int l,int r,int pos1,int pos2,int v)//更新一维，pos1为要更新的一维下标，pos2为要更新的二维下标
    {
        if(l!=r)//如果没找到一维下标，继续二分
        {
            int mid=M;
            if(pos1<=M)
                update2(lson,l,mid,pos1,pos2,v);
            else
                update2(rson,mid+1,r,pos1,pos2,v);
        }
        else
            tag=1;//打上标记
        update1(k,1,n,pos2,1,v);
    }
    void query1(int l,int r,int k,int fk)//询问二维
    {
        if(L2<=l&&r<=R2)
        {
            que1=max(que1,maxn[fk][k]);
            que2=min(que2,minn[fk][k]);
            return;
        }
        int mid=M;
        if(R2<=mid)
            query1(l,mid,lson,fk);
        else if(L2>mid)
            query1(mid+1,r,rson,fk);
        else
        {
            query1(l,mid,lson,fk);
            query1(mid+1,r,rson,fk);
        }
    }
    void query2(int l,int r,int k)//询问一维
    {
        if(L1<=l&&r<=R1)
        {
            query1(1,n,1,k);
            return;
        }
        int mid=M;
        if(R1<=mid)
            query2(l,mid,lson);
        else if(L1>mid)
            query2(mid+1,r,rson);
        else
        {
            query2(l,mid,lson);
            query2(mid+1,r,rson);
        }
    }
    int main()
    {
        int i,j,k,t,q,x,m,y,x1,y1,x2,y2,l;
        scanf("%d",&t);
        for(q=1;q<=t;q++)
        {
            scanf("%d",&n);
            for(i=1;i<=n;i++)
            {
                for(j=1;j<=n;j++)
                {
                    tag=0;//每次清0
                    scanf("%d",&x);
                    update2(1,1,n,i,j,x);
                }
            }
            printf("Case #%d:\n",q);
            scanf("%d",&m);
            while(m--)
            {
                scanf("%d%d%d",&x,&y,&l);
                l/=2;
                tag=0;
                L1=max(1,x-l);R1=min(n,x+l);//这里和之前的博客差不多了
                L2=max(1,y-l);R2=min(n,y+l);
                que1=-INF;
                que2=INF;
                query2(1,n,1);
                int val=(que1+que2)/2;
                printf("%d\n",val);
                update2(1,1,n,x,y,val);
            }
        }
        return 0;
    }

[http_blog.csdn.net_qq_37497322_article_details_77165175]: http://blog.csdn.net/qq_37497322/article/details/77165175
[http_blog.csdn.net_qq_37497322_article_details_77094852]: http://blog.csdn.net/qq_37497322/article/details/77094852