2015
09-18

# Mosaic

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?

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.��

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.��

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

Case #1:
5
6
3
4
6

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int maxn=810;
struct SNode
{
int l;
int r;
int smax;
int smin;
int getmid()
{
return (l+r)>>1;
}
};
struct Node
{
int l;
int r;
SNode t[maxn*4];
int getmid()
{
return (l+r)>>1;
}
}t[maxn*4];
int n,m,a[maxn][maxn];
void BuildY(int l,int r,int index,int p,int flag)
{
t[p].t[index].l=l;
t[p].t[index].r=r;
if(l==r)
{
if(flag)
{
t[p].t[index].smax=max(t[p<<1].t[index].smax,t[p<<1|1].t[index].smax);
t[p].t[index].smin=min(t[p<<1].t[index].smin,t[p<<1|1].t[index].smin);
}
else
t[p].t[index].smin=t[p].t[index].smax=a[t[p].l][l];
return;
}
int mid=(l+r)>>1;
BuildY(l,mid,index<<1,p,flag);
BuildY(mid+1,r,index<<1|1,p,flag);
t[p].t[index].smax=max(t[p].t[index<<1].smax,t[p].t[index<<1|1].smax);
t[p].t[index].smin=min(t[p].t[index<<1].smin,t[p].t[index<<1|1].smin);
}
void BuildX(int l,int r,int index)
{
t[index].l=l;
t[index].r=r;
if(l==r)
{
BuildY(1,n,1,index,0);
return;
}
int mid=t[index].getmid();
BuildX(l,mid,index<<1);
BuildX(mid+1,r,index<<1|1);
BuildY(1,n,1,index,1);
}
int QueryMaxY(int l,int r,int index,int p)
{
if(t[p].t[index].l==l&&t[p].t[index].r==r)
return t[p].t[index].smax;
int mid=t[p].t[index].getmid();
if(r<=mid)
return QueryMaxY(l,r,index<<1,p);
else if(l>mid)
return QueryMaxY(l,r,index<<1|1,p);
else
return max(QueryMaxY(l,mid,index<<1,p),QueryMaxY(mid+1,r,index<<1|1,p));
}
int QueryMaxX(int l,int r,int x,int y,int index)
{
if(t[index].l==l&&t[index].r==r)
return QueryMaxY(x,y,1,index);
int mid=(t[index].l+t[index].r)>>1;
if(r<=mid)
return QueryMaxX(l,r,x,y,index<<1);
else if(l>mid)
return QueryMaxX(l,r,x,y,index<<1|1);
else
return max(QueryMaxX(l,mid,x,y,index<<1),QueryMaxX(mid+1,r,x,y,index<<1|1));
}
int QueryMinY(int l,int r,int index,int p)
{
if(t[index].l==l&&t[index].r==r)
return t[p].t[index].smin;
int mid=(t[p].t[index].l+t[p].t[index].r)>>1;
if(r<=mid)
return QueryMinY(l,r,index<<1,p);
else if(l>mid)
return QueryMinY(l,r,index<<1|1,p);
else
return min(QueryMinY(l,mid,index<<1,p),QueryMinY(mid+1,r,index<<1|1,p));
}
int QueryMinX(int l,int r,int x,int y,int index)
{
if(t[index].l==l&&t[index].r==r)
return QueryMinY(x,y,1,index);
int mid=(t[index].l+t[index].r)>>1;
if(r<=mid)
return QueryMinX(l,r,x,y,index<<1);
else if(l>mid)
return QueryMinX(l,r,x,y,index<<1|1);
else
return min(QueryMinX(l,mid,x,y,index<<1),QueryMinX(mid+1,r,x,y,index<<1|1));
}
void ModifyY(int y,int index,int val,int p,int flag)
{
if(t[p].t[index].l==t[p].t[index].r)
{
if(!flag)
t[p].t[index].smin=t[p].t[index].smax=val;
else
{
t[p].t[index].smin=min(t[p<<1].t[index].smin,t[p<<1|1].t[index].smin);
t[p].t[index].smax=max(t[p<<1].t[index].smax,t[p<<1|1].t[index].smax);
}
return;
}
int mid=(t[p].t[index].l+t[p].t[index].r)>>1;
if(y<=mid)
ModifyY(y,index<<1,val,p,flag);
else
ModifyY(y,index<<1|1,val,p,flag);
t[p].t[index].smax=max(t[p].t[index<<1].smax,t[p].t[index<<1|1].smax);
t[p].t[index].smin=min(t[p].t[index<<1].smin,t[p].t[index<<1|1].smin);
}
void ModifyX(int x,int y,int index,int val)
{
if(t[index].l==t[index].r)
{
ModifyY(y,1,val,index,0);
return;
}
int mid=(t[index].l+t[index].r)>>1;
if(x<=mid)
ModifyX(x,y,index<<1,val);
else
ModifyX(x,y,index<<1|1,val);
ModifyY(y,1,val,index,1);
}
int main()
{
int T,cas=1;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%d",&a[i][j]);
BuildX(1,n,1);
scanf("%d",&m);
printf("Case #%d:\n",cas++);
while(m--)
{
int x,y,l;
scanf("%d%d%d",&x,&y,&l);
int sx=max(1,x-l/2);
int sy=max(1,y-l/2);
int mx=min(n,x+l/2);
int my=min(n,y+l/2);
int smax=QueryMaxX(sx,mx,sy,my,1);
int smin=QueryMinX(sx,mx,sy,my,1);
printf("%d\n",(smax+smin)>>1);
ModifyX(x,y,1,(smax+smin)>>1);
}
}
return 0;
}


1. 碳酸泡腾片不是什么新东西，但和瓶盖结合有新意，然并卵。会想喝的人随身带泡腾片也不麻烦，不想喝的人等于用几倍价钱买水。

2. 超AｰVictoria Beckham(维多利亚·贝克汉姆)Stuart Weitzman(斯图尔特●韦茨曼/小辣椒 )YSL(圣罗兰)cheap monday(便宜星期一)yuandan.gq

3. ꝸꝸꝸꝸꝸꝸꝸꝸꝸ丝袜会所ꝸꝸꝸꝸꝸꝸꝸꝸꝸꝸꝸꝸꝸꝸꝸꝸꝸꝸ操丝袜脚ꝸꝸꝸꝸꝸꝸꝸꝸꝸꝸꝸꝸꝸꝸꝸꝸꝸꝸ高跟玉足ꝸꝸꝸꝸꝸꝸꝸꝸꝸꝸꝸꝸꝸꝸꝸꝸꝸꝸ成人丝袜dvdꝸꝸꝸꝸꝸꝸꝸꝸꝸꝸꝸꝸꝸꝸꝸꝸꝸꝸ街拍短丝袜ꝸꝸꝸꝸꝸꝸꝸꝸꝸꝸꝸꝸꝸꝸꝸꝸꝸꝸ街拍黑丝袜ꝸꝸꝸꝸꝸꝸꝸꝸꝸhTTp://T.cN/R6IQBNS

4. ＾＾＾＾＾＾＾＾丝袜美脚＾＾＾＾＾＾＾＾＾＾＾＾＾＾＾＾紫色丝袜＾＾＾＾＾＾＾＾＾＾＾＾＾＾＾＾恋玉足＾＾＾＾＾＾＾＾＾＾＾＾＾＾＾＾美足交＾＾＾＾＾＾＾＾＾＾＾＾＾＾＾＾强撕女服务员丝袜＾＾＾＾＾＾＾＾www.meitui1.com