Approach : Segment Tree , Sqrt-Decomposition..
First Solution :
This is typical 2D segment tree problem. Just write the code correctly and good enough to get AC
I used two array , One to store Maximum , One to Minimum ..
#include <bits/stdc++.h>
using namespace std;
/*------- Constants---- */
#define LMT 605
#define ll long long
#define ull unsigned long long
#define mod 1000000007
#define MEMSET_INF 63
#define MEM_VAL 1061109567
#define FOR(i,n) for( int i=0 ; i < n ; i++ )
#define mp(i,j) make_pair(i,j)
#define lop(i,a,b) for( int i = (a) ; i < (b) ; i++)
#define pb(a) push_back((a))
#define gc getchar_unlocked
#define PI acos(-1.0)
#define inf 1<<30
#define lc ((n)<<1)
#define rc ((n)<<1 |1)
#define msg(x) cout<<x<<endl;
/*---- short Cuts ------- */
#define ms(ara_name,value) memset(ara_name,value,sizeof(ara_name))
typedef pair<int, int> ii;
typedef vector<int > vi ;
/*------ template functions ------ */
inline void sc(int &x)
{
register int c = gc();
x = 0;
int neg = 0;
for(;((c<48 | c>57) && c != '-');c = gc());
if(c=='-') {neg=1;c=gc();}
for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
if(neg) x=-x;
}
template <class T> inline T bigmod(T p,T e,T M){
ll ret = 1;
for(; e > 0; e >>= 1){
if(e & 1) ret = (ret * p) % M;
p = (p * p) % M;
} return (T)ret;
}
template <class T> inline T gcd(T a,T b){if(b==0)return a;return gcd(b,a%b);}
template <class T> inline T modinverse(T a,T M){return bigmod(a,M-2,M);}
/*************************** END OF TEMPLATE ****************************/
int t[4*LMT][4*LMT];
int p[4*LMT][4*LMT];
int a[LMT][LMT];
int m , n ;
void build_y (int vx, int lx, int rx, int vy, int ly, int ry) {
if (ly == ry)
if (lx == rx){
t[vx][vy] = a[lx][ly];
p[vx][vy] = a[lx][ly];
}
else {
t[vx][vy] = max(t[vx*2][vy] , t[vx*2+1][vy] );
p[vx][vy] = min(p[vx*2][vy] , p[vx*2+1][vy] );
}
else {
int my = (ly + ry) / 2;
build_y (vx, lx, rx, vy*2, ly, my);
build_y (vx, lx, rx, vy*2+1, my+1, ry);
t[vx][vy] = max(t[vx][vy *2] , t[vx][vy *2 + 1]);
p[vx][vy] = min(p[vx][vy *2] , p[vx][vy *2 + 1]);
}
}
void build_x (int vx, int lx, int rx) {
if (lx != rx) {
int mx = (lx + rx) / 2;
build_x (vx*2, lx, mx);
build_x (vx*2+1, mx+1, rx);
}
build_y (vx, lx, rx, 1, 0, m-1);
}
void update_y (int vx, int lx, int rx, int vy, int ly, int ry, int x, int y, int new_val) {
if (ly == ry) {
if (lx == rx){
t[vx][vy] = new_val;
p[vx][vy] = new_val;
}
else {
t[vx][vy] = max(t[vx*2][vy] , t[vx*2+1][vy] );
p[vx][vy] = min(p[vx*2][vy] , p[vx*2+1][vy] );
}
}
else {
int my = (ly + ry) / 2;
if (y <= my) update_y (vx, lx, rx, vy*2, ly, my, x, y, new_val);
else update_y (vx, lx, rx, vy*2+1, my+1, ry, x, y, new_val);
t[vx][vy] = max(t[vx][vy *2] , t[vx][vy *2 + 1]);
p[vx][vy] = min(p[vx][vy *2] , p[vx][vy *2 + 1]);
}
}
void update_x (int vx, int lx, int rx, int x, int y, int new_val) {
if (lx != rx) {
int mx = (lx + rx) / 2;
if (x <= mx) update_x (vx*2, lx, mx, x, y, new_val);
else update_x (vx*2+1, mx+1, rx, x, y, new_val);
}
update_y (vx, lx, rx, 1, 0, m-1, x, y, new_val);
}
ii query_y (int vx, int vy, int tly, int try_, int ly, int ry) {
if (ly > ry) return ii(-1,inf );
if (ly == tly && try_ == ry) return ii( t[vx][vy] ,p[vx][vy]);
int tmy = (tly + try_) / 2;
ii r1 = query_y (vx, vy*2, tly, tmy, ly, min(ry,tmy));
ii r2 = query_y (vx, vy*2+1, tmy+1, try_, max(ly,tmy+1), ry);
return ii( max(r1.first , r2.first) , min(r1.second, r2.second)) ;
}
ii query_x (int vx, int tlx, int trx, int lx, int rx, int ly, int ry) {
if (lx > rx)
return ii(-1,inf );
if (lx == tlx && trx == rx)
return query_y (vx, 1, 0, m-1, ly, ry);
int tmx = (tlx + trx) / 2;
ii r1 = query_x (vx*2, tlx, tmx, lx, min(rx,tmx), ly, ry);
ii r2 = query_x (vx*2+1, tmx+1, trx, max(lx,tmx+1), rx, ly, ry);
return ii( max(r1.first , r2.first) , min(r1.second, r2.second)) ;
}
int val ;
int main()
{
int q ;
sc(n); sc(m);
FOR(i , n) FOR(j , m) sc(a[i][j]);
build_x(1, 0 , n-1);
sc(q);
char ch ;
int x1, x2 , y1 , y2;
while (q -- ) {
do {
ch = gc();
} while (ch =='\n'||ch =='\0');
if(ch == 'q') {
sc(x1) ; sc(y1) ;sc(x2);sc(y2);
x1 -- , y1 -- ,x2 -- , y2 --;
ii r = query_x( 1, 0 , n -1 , x1 , x2 , y1 , y2);
printf("%d %d\n" ,r.first , r.second);
}
else {
sc(x1) ;sc(y1 );sc(val);
x1 -- , y1--;
update_x(1, 0, n-1 ,x1 , y1,val);
}
}
return 0;
}
Second Try : Sqrt- Decompostion.
1. We can divide the whole square / Rectangle in some smaller block which dimension is sqrt(n) x sqrt(n)
2. We store The minimum & maximum of this block in a 2D array ..
3. For updating a point We need just to update the block , where it belongs,
4. For query , We need to traverse thorough lot of case …
Please See the implementation And try to understand how the whole interval is covered.
#include <bits/stdc++.h>
using namespace std;
/*------- Constants---- */
#define LMT 600
#define ll long long
#define ull unsigned long long
#define mod 1000000007
#define MEMSET_INF 63
#define MEM_VAL 1061109567
#define FOR(i,n) for( int i=0 ; i < n ; i++ )
#define mp(i,j) make_pair(i,j)
#define lop(i,a,b) for( int i = (a) ; i < (b) ; i++)
#define pb(a) push_back((a))
#define gc getchar_unlocked
#define PI acos(-1.0)
#define inf 1<<30
#define lc ((n)<<1)
#define rc ((n)<<1 |1)
#define msg(x) cout<<x<<endl;
/*---- short Cuts ------- */
#define ms(ara_name,value) memset(ara_name,value,sizeof(ara_name))
typedef pair<int, int> ii;
typedef vector<int > vi ;
/*------ template functions ------ */
inline void sc(int &x)
{
register int c = gc();
x = 0;
int neg = 0;
for(;((c<48 | c>57) && c != '-');c = gc());
if(c=='-') {neg=1;c=gc();}
for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
if(neg) x=-x;
}
template <class T> inline T bigmod(T p,T e,T M){
ll ret = 1;
for(; e > 0; e >>= 1){
if(e & 1) ret = (ret * p) % M;
p = (p * p) % M;
} return (T)ret;
}
template <class T> inline T gcd(T a,T b){if(b==0)return a;return gcd(b,a%b);}
template <class T> inline T modinverse(T a,T M){return bigmod(a,M-2,M);}
/*************************** END OF TEMPLATE ****************************/
int block ;
int iA[LMT][LMT];
int partMax[35][35];
int partMin[35][35];
int val;
int main()
{
int n , m ;
sc(n ); sc(m );
block = sqrt(n) + 1 ;
FOR(i, block + 5 ){
FOR(j , block + 5 ){
partMax[i][j] = -1;
partMin[i][j] = inf;
}
}
FOR(i, n) {
int x = i / block;
FOR(j, m){
sc(iA[i][j]);
partMax [x][j/block] = max( partMax[x][j / block] , iA[i][j] );
partMin [x][j/block] = min( partMin[x][j / block] , iA[i][j] );
}
}
int q , x1 , y1 , x2 , y2 ;
char ch ;
sc(q);
int cnt= 0;
while (q -- ) {
do {
ch = gc();
} while (ch =='\n'||ch =='\0');
if(ch == 'q') {
++cnt;
if(cnt == 12 ) {
//cout<<""<<endl;
}
sc(x1) ;sc(y1) ;sc(x2) ; sc(y2);
x1 -- , y1 -- , x2 -- , y2 --;
int iMac = -1 , iMin = inf ;
while(x1 <= x2 && x1 % block != 0 ){
for(int j = y1 ; j <= y2 ; j ++ ) {
iMac = max(iMac , iA[x1][j]);
iMin = min(iMin , iA[x1][j]);
}
x1 ++;
}
while (x1 + block - 1 <= x2 ) {
int y = y1;
while (y <= y2 && y % block != 0 ) {
for(int i = x1; i < x1 + block ; i ++ ) {
iMac = max(iMac , iA[i][y]);
iMin = min(iMin , iA[i][y]);
}
y ++;
}
while (y + block -1 <= y2 ) {
iMac = max(iMac , partMax[x1/block][y /block]);
iMin = min(iMin , partMin[x1/block][y/block]);
y += block;
}
while( y <= y2 ) {
for(int i = x1; i < x1 + block ; i ++ ) {
iMac = max(iMac , iA[i][y]);
iMin = min(iMin , iA[i][y]);
}
y ++;
}
x1 = x1 + block;
}
for(int i = x1 ; i <= x2; i ++ ){
for (int j = y1 ; j <= y2 ; j ++ ) {
iMac = max(iMac , iA[i][j]);
iMin = min(iMin , iA[i][j]);
}
}
printf("%d %d\n",iMac , iMin);
}
else {
sc(x1) ; sc(y1 ); sc(val);
x1 -- ;
y1 -- ;
iA[x1][y1] = val;
int i = (x1 / block ) * block;
int j = (y1 / block ) * block;
partMax[i/block][j /block] = 0;
partMin[i/block][j/block] = inf;
for(int L = i ; L < i+ block ; L ++ ) {
int x = L / block;
for (int R = j ; R < j + block ; R ++ ) {
partMax[x][R / block] = max ( partMax[x][R /block ] , iA[L][R]);
partMin[x][R / block] = min ( partMin[x][R /block ] , iA[L][R]);
}
}
}
}
return 0;
}
Third Approach :
Maintain 1D segment tree for Each Row.
This one is the easiest one. And also get AC in given time limit..
1. For each row, Maintain a segment tree to so that you can find minimum and maximum value in a given interval.
2. For query operation, iterate through the row , and find the minimum and Maximum Value in the given (y1,y2) interval
See the implementation:
#include <bits/stdc++.h>
using namespace std;
/*------- Constants---- */
#define LMT 605
#define ll long long
#define ull unsigned long long
#define mod 1000000007
#define MEMSET_INF 63
#define MEM_VAL 1061109567
#define FOR(i,n) for( int i=0 ; i < n ; i++ )
#define mp(i,j) make_pair(i,j)
#define lop(i,a,b) for( int i = (a) ; i < (b) ; i++)
#define pb(a) push_back((a))
#define gc getchar_unlocked
#define PI acos(-1.0)
#define inf 1<<30
#define lc ((n)<<1)
#define rc ((n)<<1 |1)
#define msg(x) cout<<x<<endl;
/*---- short Cuts ------- */
#define ms(ara_name,value) memset(ara_name,value,sizeof(ara_name))
typedef pair<int, int> ii;
typedef vector<int > vi ;
/*------ template functions ------ */
inline void sc(int &x)
{
register int c = gc();
x = 0;
int neg = 0;
for(;((c<48 | c>57) && c != '-');c = gc());
if(c=='-') {neg=1;c=gc();}
for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
if(neg) x=-x;
}
template <class T> inline T bigmod(T p,T e,T M){
ll ret = 1;
for(; e > 0; e >>= 1){
if(e & 1) ret = (ret * p) % M;
p = (p * p) % M;
} return (T)ret;
}
template <class T> inline T gcd(T a,T b){if(b==0)return a;return gcd(b,a%b);}
template <class T> inline T modinverse(T a,T M){return bigmod(a,M-2,M);}
/*************************** END OF TEMPLATE ****************************/
ii seg[LMT][4*LMT];
int row;
int val;
int iA[LMT][LMT];
void build(int n,int b,int e)
{
if( b == e) {
seg[row][n] = ii(iA[row][b] , iA[row][b]);
return;
}
int mid = (b+e)/2;
build(lc, b, mid);
build(rc, mid +1 , e);
seg[row][n].first = max( seg[row][lc].first , seg[row][rc].first );
seg[row][n].second = min (seg[row][lc].second , seg[row][rc].second);
}
void updt(int n,int b,int e,int pos)
{
if( b == e && b == pos ) {
seg[row][n].first = val;
seg[row][n].second = val;
return;
}
int mid = (b+e)/2;
if( pos <= mid ) updt(lc , b , mid , pos);
else updt(rc, mid + 1, e, pos);
seg[row][n].first = max( seg[row][lc].first , seg[row][rc].first );
seg[row][n].second = min (seg[row][lc].second , seg[row][rc].second);
}
ii query(int n,int b,int e ,int i , int j )
{
if( b > j || e < i) return ii(-1,inf);
if( b >= i && e <= j ) {
return seg[row][n];
}
int mid = (b+e) / 2;
ii r1 = query(lc , b , mid, i, j);
ii r2 = query(rc , mid + 1, e, i , j);
return ii(max(r1.first , r2.first) , min(r1.second , r2.second));
}
int main()
{
int n , m ,q ;
sc(n) ;sc(m);
FOR(i, n){
row = i;
FOR(j, m) {
sc(iA[i][j]);
}
build(1, 0 , m -1);
}
sc(q);
char ch;
int x1, x2 , y1 , y2;
while (q -- ) {
do {
ch =gc();
} while (ch == '\n' || ch =='\0');
if(ch =='q'){
sc(x1) ;sc(y1) ;sc(x2); sc(y2);
x1--,y1--,x2--,y2--;
ii r = ii(-1,inf);
for(int i = x1; i <= x2; i ++ ) {
row = i ;
ii r1 = query(1, 0, m-1, y1 , y2);
r.first = max(r.first , r1.first);
r.second = min(r.second , r1.second);
}
printf("%d %d\n" , r.first , r.second);
}
if( ch =='c'){
sc(x1);sc(y1) ;sc(val);
x1 -- ,y1--;
row = x1;
updt(1, 0, n-1, y1);
}
}
return 0;
}
I hope there may be other methods to solve this problem . Explore them..
Remark :
2D segment Tree is the best solution
Sqrt Decomposition
Row Based 1D segment Tree
Code for Fun 