UVA 11279 Census Solution in Java using 2D Segment Tree

import java.io.*;
class Census
{
static int a[][];
static class Segtree
{
int n;
int m;
int p[];
int p1[];
Segtree(int n,int m)
{
this.n=n;
this.m=m;
p=new int[2*506*506];
p1=new int[2*506*506];
build(1,1,1,n,m);
build1(1,1,1,n,m);
}
void build(int node,int a1,int b1,int a2,int b2)
{
if((a1>a2) || (b1>b2))
p[node]=-1;
else if((a1==a2) && (b1==b2))
{

p[node]=a[a1][b1];
}
else
{
p[node]=-1;
build(4*node-2,a1,b1,(a1+a2)/2,(b1+b2)/2);
p[node]=max(p[node],p[4*node-2]);
build(4*node-1,(a1+a2)/2+1,b1,a2,(b1+b2)/2);
p[node]=max(p[node],p[4*node-1]);
build(4*node,a1,(b1+b2)/2+1,(a1+a2)/2,b2);
p[node]=max(p[node],p[4*node]);
build(4*node+1,(a1+a2)/2+1,(b1+b2)/2+1,a2,b2);
p[node]=max(p[node],p[4*node+1]);

}
}
void update(int node,int a1,int b1,int a2,int b2,int x,int y,int value)
{
if(a1>a2 || b1>b2|| x<a1||x>a2||y<b1||y>b2 )
return;
if(a1==x && a2==x && b1==y && b2==y)
p[node]=value;
else
{
int v=-1;
update(4*node-2,a1,b1,(a1+a2)/2,(b1+b2)/2,x,y,value);
v=max(v,p[4*node-2]);
update(4*node-1,(a1+a2)/2+1,b1,a2,(b1+b2)/2,x,y,value);
v=max(v,p[4*node-1]);
update(4*node,a1,(b1+b2)/2+1,(a1+a2)/2,b2,x,y,value);//3
v=max(v,p[4*node]);
update(4*node+1,(a1+a2)/2+1,(b1+b2)/2+1,a2,b2,x,y,value);
v=max(v,p[4*node+1]);
p[node]=v;
}

}
void update1(int node,int a1,int b1,int a2,int b2,int x,int y,int value)
{
if(a1>a2 || b1>b2|| x<a1||x>a2||y<b1||y>b2)
return;
if(a1==x && a2==x && b1==y && b2==y)
p1[node]=value;
else
{
int v=1<<30;
update1(4*node-2,a1,b1,(a1+a2)/2,(b1+b2)/2,x,y,value);
v=min(v,p1[4*node-2]);
update1(4*node-1,(a1+a2)/2+1,b1,a2,(b1+b2)/2,x,y,value);
v=min(v,p1[4*node-1]);
update1(4*node,a1,(b1+b2)/2+1,(a1+a2)/2,b2,x,y,value);
v=min(v,p1[4*node]);
update1(4*node+1,(a1+a2)/2+1,(b1+b2)/2+1,a2,b2,x,y,value);
v=min(v,p1[4*node+1]);
p1[node]=v;
}

}
void build1(int node,int a1,int b1,int a2,int b2)
{
if((a1>a2) || (b1>b2))
p1[node]=1<<30;
else if((a1==a2) && (b1==b2))
{

p1[node]=a[a1][b1];
}
else
{
p1[node]=1<<30;
build1(4*node-2,a1,b1,(a1+a2)/2,(b1+b2)/2);
p1[node]=min(p1[node],p1[4*node-2]);
build1(4*node-1,(a1+a2)/2+1,b1,a2,(b1+b2)/2);
p1[node]=min(p1[node],p1[4*node-1]);
build1(4*node,a1,(b1+b2)/2+1,(a1+a2)/2,b2);
p1[node]=min(p1[node],p1[4*node]);
build1(4*node+1,(a1+a2)/2+1,(b1+b2)/2+1,a2,b2);
p1[node]=min(p1[node],p1[4*node+1]);

}
}
int max(int a,int b)
{
if(a>b)
return a;
else
return b;
}
int min(int a,int b)
{
if(a<b)
return a;
else
return b;
}
int query(int node,int a1,int b1,int a2,int b2,int x1,int y1,int x2,int y2 )
{

if(a2<x1 || a1>x2 || b2<y1 || b1>y2 || a1>a2 || b1>b2)
return -1;
else if(a1>=x1 && a2<=x2 && b1>=y1 && b2<=y2)
return p[node];
else
{
int v=-1;
v=max(v,query(4*node-2,a1,b1,(a1+a2)/2,(b1+b2)/2,x1,y1,x2,y2));
v=max(v,query(4*node-1,(a1+a2)/2+1,b1,a2,(b1+b2)/2,x1,y1,x2,y2));
v=max(v,query(4*node,a1,(b1+b2)/2+1,(a1+a2)/2,b2,x1,y1,x2,y2));
v=max(v,query(4*node+1,(a1+a2)/2+1,(b1+b2)/2+1,a2,b2,x1,y1,x2,y2));
return v;
}


}
int query1(int node,int a1,int b1,int a2,int b2,int x1,int y1,int x2,int y2 )
{

if(a2<x1 || a1>x2 || b2<y1 || b1>y2 || a1>a2 || b1>b2)
return 1<<30;
else if(a1>=x1 && a2<=x2 && b1>=y1 && b2<=y2)
return p1[node];
else
{
int v=1<<30;
v=min(v,query1(4*node-2,a1,b1,(a1+a2)/2,(b1+b2)/2,x1,y1,x2,y2));
v=min(v,query1(4*node-1,(a1+a2)/2+1,b1,a2,(b1+b2)/2,x1,y1,x2,y2));
v=min(v,query1(4*node,a1,(b1+b2)/2+1,(a1+a2)/2,b2,x1,y1,x2,y2));
v=min(v,query1(4*node+1,(a1+a2)/2+1,(b1+b2)/2+1,a2,b2,x1,y1,x2,y2));
return v;
}


}


}


public static void main(String[] args) throws IOException
{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));


int n=Integer.parseInt(br.readLine());
int m=n;

a=new int[n+1][m+1];
int i=0;
int tem=n;
while(tem-->0)
{
i++;
String t[]=br.readLine().split(" ");
for(int j=1;j<=m;j++)
{

a[i][j]=Integer.parseInt(t[j-1]);
}
}
Segtree st=new Segtree(n,m);
int q=Integer.parseInt(br.readLine());
while(q-- >0)
{
String que[]=br.readLine().split(" ");
if(que.length==5)
{
int x1=Integer.parseInt(que[1]);
int y1=Integer.parseInt(que[2]);
int x2=Integer.parseInt(que[3]);
int y2=Integer.parseInt(que[4]);
System.out.println(st.query(1,1,1,n,m,x1, y1, x2, y2)+" "+st.query1(1,1,1,n,m,x1, y1, x2, y2));

}
else
{
int x1=Integer.parseInt(que[1]);
int y1=Integer.parseInt(que[2]);
int v=Integer.parseInt(que[3]);
st.update(1,1,1,n,m,x1,y1,v);
st.update1(1,1,1,n,m,x1,y1,v);

}
}



}

}