Mosaic
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 102400/102400 K (Java/Others)
Total Submission(s): 647 Accepted Submission(s): 245
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?
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.
For each action, print the new color value of the updated cell.
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<algorithm>
#include<iostream>
#include<string.h>
#include<stdio.h>
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=810;
typedef long long ll;
#define lson L,mid,ls
#define rson mid+1,R,rs
struct Tree
{
int mav[maxn<<2][maxn<<2],miv[maxn<<2][maxn<<2];
int n,m,x,y,val,isleaf,x1,y1,x2,y2,xrt,amav,amiv;
void buildy(int L,int R,int rt)
{
if(L==R)
{
if(isleaf)
{
scanf("%d",&mav[xrt][rt]);
miv[xrt][rt]=mav[xrt][rt];
}
else
{
mav[xrt][rt]=max(mav[xrt<<1][rt],mav[xrt<<1|1][rt]);
miv[xrt][rt]=min(miv[xrt<<1][rt],miv[xrt<<1|1][rt]);
}
return;
}
int ls=rt<<1,rs=ls|1,mid=(L+R)>>1;
buildy(lson);
buildy(rson);
mav[xrt][rt]=max(mav[xrt][ls],mav[xrt][rs]);
miv[xrt][rt]=min(miv[xrt][ls],miv[xrt][rs]);
}
void buildx(int L,int R,int rt)
{
if(L==R)
{
xrt=rt,isleaf=1;
buildy(1,m,1);
return;
}
int ls=rt<<1,rs=ls|1,mid=(L+R)>>1;
buildx(lson);
buildx(rson);
xrt=rt,isleaf=0;
buildy(1,m,1);
}
void build(int nn,int mm)
{
n=nn,m=mm;
buildx(1,n,1);
}
void updatey(int L,int R,int rt)
{
if(L==R)
{
if(isleaf)
mav[xrt][rt]=miv[xrt][rt]=val;
else
{
mav[xrt][rt]=max(mav[xrt<<1][rt],mav[xrt<<1|1][rt]);
miv[xrt][rt]=min(miv[xrt<<1][rt],miv[xrt<<1|1][rt]);
}
return;
}
int ls=rt<<1,rs=ls|1,mid=(L+R)>>1;
if(y<=mid)
updatey(lson);
else
updatey(rson);
mav[xrt][rt]=max(mav[xrt][ls],mav[xrt][rs]);
miv[xrt][rt]=min(miv[xrt][ls],miv[xrt][rs]);
}
void updatex(int L,int R,int rt)
{
if(L==R)
{
xrt=rt,isleaf=1;
updatey(1,m,1);
return;
}
int ls=rt<<1,rs=ls|1,mid=(L+R)>>1;
if(x<=mid)
updatex(lson);
else
updatex(rson);
xrt=rt,isleaf=0;
updatey(1,m,1);
}
void update(int xx,int yy,int v)
{
x=xx,y=yy,val=v;
updatex(1,n,1);
}
void queryy(int L,int R,int rt)
{
if(y1<=L&&R<=y2)
{
amav=max(amav,mav[xrt][rt]);
amiv=min(amiv,miv[xrt][rt]);
return;
}
int ls=rt<<1,rs=ls|1,mid=(L+R)>>1;
if(y1<=mid)
queryy(lson);
if(y2>mid)
queryy(rson);
}
void queryx(int L,int R,int rt)
{
if(x1<=L&&R<=x2)
{
xrt=rt;
queryy(1,m,1);
return;
}
int ls=rt<<1,rs=ls|1,mid=(L+R)>>1;
if(x1<=mid)
queryx(lson);
if(x2>mid)
queryx(rson);
}
void query(int xx1,int yy1,int xx2,int yy2)
{
x1=xx1,y1=yy1,x2=xx2,y2=yy2;
amav=-1,amiv=INF;
queryx(1,n,1);
}
} tree;
int main()
{
int t,cas=1,n,m,i,x,y,len,x1,y1,x2,y2,ans;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
tree.build(n,n);
printf("Case #%d:\n",cas++);
scanf("%d",&m);
for(i=0;i<m;i++)
{
scanf("%d%d%d",&x,&y,&len);
len=len>>1;
x1=max(1,x-len),y1=max(1,y-len);
x2=min(n,x+len),y2=min(n,y+len);
tree.query(x1,y1,x2,y2);
ans=(tree.amav+tree.amiv)>>1;
tree.update(x,y,ans);
printf("%d\n",ans);
}
}
return 0;
}
用自己以前的想法写了一发。还是过了。不过用时多一点。以前我想的就是把平面分成四份。
#include<algorithm>
#include<iostream>
#include<string.h>
#include<stdio.h>
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=810*810;
typedef long long ll;
#define lson L,mid,ls
#define rson mid+1,R,rs
int mav[maxn<<2],miv[maxn<<2],x,y,val,x1,y1,x2,y2,amav,amiv;
void update(int U,int D,int L,int R,int rt)
{
if(U==D&&L==R)
{
mav[rt]=miv[rt]=val;
return;
}
int xmid=(U+D)>>1,ymid=(L+R)>>1,ss=rt<<2;
if(U==D)
{
if(y<=ymid)
update(U,D,L,ymid,ss-2);
else
update(U,D,ymid+1,R,ss-1);
mav[rt]=max(mav[ss-2],mav[ss-1]);
miv[rt]=min(miv[ss-2],miv[ss-1]);
return;
}
if(L==R)
{
if(x<=xmid)
update(U,xmid,L,R,ss-2);
else
update(xmid+1,D,L,R,ss);
mav[rt]=max(mav[ss-2],mav[ss]);
miv[rt]=min(miv[ss-2],miv[ss]);
return;
}
if(x<=xmid)
{
if(y<=ymid)
update(U,xmid,L,ymid,ss-2);
else
update(U,xmid,ymid+1,R,ss-1);
}
else
{
if(y<=ymid)
update(xmid+1,D,L,ymid,ss);
else
update(xmid+1,D,ymid+1,R,ss+1);
}
mav[rt]=max(max(mav[ss-2],mav[ss-1]),max(mav[ss],mav[ss+1]));
miv[rt]=min(min(miv[ss-2],miv[ss-1]),min(miv[ss],miv[ss+1]));
}
void qu(int U,int D,int L,int R,int rt)
{
if(x1<=U&&D<=x2&&y1<=L&&R<=y2)
{
amav=max(amav,mav[rt]);
amiv=min(amiv,miv[rt]);
return;
}
int xmid=(U+D)>>1,ymid=(L+R)>>1,ss=rt<<2;
if(U==D)
{
if(y1<=ymid)
qu(U,D,L,ymid,ss-2);
if(y2>ymid)
qu(U,D,ymid+1,R,ss-1);
return;
}
if(L==R)
{
if(x1<=xmid)
qu(U,xmid,L,R,ss-2);
if(x2>xmid)
qu(xmid+1,D,L,R,ss);
return;
}
if(x1<=xmid&&y1<=ymid)
qu(U,xmid,L,ymid,ss-2);
if(x1<=xmid&&y2>ymid)
qu(U,xmid,ymid+1,R,ss-1);
if(x2>xmid&&y1<=ymid)
qu(xmid+1,D,L,ymid,ss);
if(x2>xmid&&y2>ymid)
qu(xmid+1,D,ymid+1,R,ss+1);
}
int main()
{
int t,cas=1,n,m,i,j,len,ans;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
scanf("%d",&val);
x=i,y=j;
update(1,n,1,n,1);
}
}
printf("Case #%d:\n",cas++);
scanf("%d",&m);
for(i=0;i<m;i++)
{
scanf("%d%d%d",&x,&y,&len);
len=len>>1;
x1=max(1,x-len),y1=max(1,y-len);
x2=min(n,x+len),y2=min(n,y+len);
amiv=INF,amav=-1;
qu(1,n,1,n,1);
ans=(amav+amiv)>>1;
val=ans;
update(1,n,1,n,1);
printf("%d\n",ans);
}
}
return 0;
}