[UVa] 11297 - Census

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : 11297 - Census
Source            : UVa Online Judge
Category          : Graph Theory
Algorithm         : Segment Tree 2D
Verdict           : Accepted 

// 2D Segment Tree
// Query  : Find maximum and minimum of a rectangle (r1,c1) -> (r2,c2)
// Update : Change value of a cell (r1,c1)
 
#include "bits/stdc++.h"
 
using namespace std;
 
#define ll                 long long
#define inf                1e17
#define pll                pair <ll, ll>
#define ff                 first
#define ss                 second
 
static const int maxn = 500 + 5;
 
int row, col;
ll grid[maxn][maxn];
pll st[maxn*4][maxn*4];
 
// here we are not changing first 3 arguments. Means, our rows are fixed.
// we narrow down to our columns, and generate segment tree for row [r1,r2] (including)
// we can pass flag instead of passing two parameters r1 and r2 (thats just optimization)/
 
void genSegTreeFrom_c1_to_c2(int parSegTree, int r1, int r2, int node, int c1, int c2)
{
    if (c1 == c2)
    {
        if (r1 == r2)
        {
            // means we are working on single row,
            // and we can directly generate segment tree for that row = r1;
            st[parSegTree][node].ff = st[parSegTree][node].ss = grid[r1][c1];
            return;
        }
        // here, parSegTree      = parent segment tree
        // (parSegTree << 1)     = left child segment tree
        // (parSegTree << 1 | 1) = right child segment tree
        // we build parent segment tree using values of children segment trees
 
        // we are creating segment tree which contains sum from row (r1 to r2)
 
        if (r1 != r2)
        {
            int leftChild = parSegTree << 1;
            int rightChild = leftChild | 1;
            st[parSegTree][node].ff = min(st[leftChild][node].ff, st[rightChild][node].ff);
            st[parSegTree][node].ss = max(st[leftChild][node].ss, st[rightChild][node].ss);
            return;
        }
    }
    int left = node << 1;
    int right = left | 1;
    int mid = (c1 + c2) >> 1;
    genSegTreeFrom_c1_to_c2(parSegTree, r1, r2, left, c1, mid);
    genSegTreeFrom_c1_to_c2(parSegTree, r1, r2, right, mid+1, c2);
    st[parSegTree][node].ff = min(st[parSegTree][left].ff, st[parSegTree][right].ff);
    st[parSegTree][node].ss = max(st[parSegTree][left].ss, st[parSegTree][right].ss);
}
 
void genSegTreeFrom_r1_to_r2(int node, int r1, int r2)
{
    // if we have narrow down to single row
    if (r1 == r2)
    {
        genSegTreeFrom_c1_to_c2(node, r1, r2, 1, 1, col);
        return;
    }
    int left = node << 1;
    int right = left | 1;
    int mid = (r1 + r2) >> 1;
    genSegTreeFrom_r1_to_r2(left, r1, mid);
    genSegTreeFrom_r1_to_r2(right, mid+1, r2);
 
    // now using upper two segment trees, we create new segment tree
    genSegTreeFrom_c1_to_c2(node, r1, r2, 1, 1, col);
}
 
void gen2DSegTree()
{
    genSegTreeFrom_r1_to_r2(1, 1, row);
}
 
pll getSumFrom_c1_to_c2(int parSegTree, int node, int c1, int c2, int i, int j)
{
    if (c1 > c2 || c1 > j || c2 < i) return {inf, -inf};
    if (c1 >= i && c2 <= j) return st[parSegTree][node];
    int left = node << 1;
    int right = left | 1;
    int mid = (c1 + c2) >> 1;
    pll p = getSumFrom_c1_to_c2(parSegTree, left, c1, mid, i, j);
    pll q = getSumFrom_c1_to_c2(parSegTree, right, mid + 1, c2, i, j);
    return {min(p.ff, q.ff), max(p.ss, q.ss)};
}
 
pll getSumFrom_r1_to_r2(int node, int r1, int r2, int ri, int rj, int ci, int cj)
{
    if (r1 > r2 || r1 > rj || r2 < ri) return {inf, -inf};
    if (r1 >= ri && r2 <= rj) return getSumFrom_c1_to_c2(node, 1, 1, col, ci, cj);
    int left = node << 1;
    int right = left | 1;
    int mid = (r1 + r2) >> 1;
    pll p = getSumFrom_r1_to_r2(left, r1, mid, ri, rj, ci, cj);
    pll q = getSumFrom_r1_to_r2(right, mid + 1, r2, ri, rj, ci, cj);
    return {min(p.ff, q.ff), max(p.ss, q.ss)};
}
 
pll query(int r1, int c1, int r2, int c2)
{
    return getSumFrom_r1_to_r2(1, 1, row, r1, r2, c1, c2);
}
 
void updateSegTreeIn_cx(int parSegTree, int r1, int r2, int node, int c1, int c2, int y, ll value)
{
    if (c1 > c2 || c1 > y || c2 < y) return;
    if (c1 >= y && c2 <= y)
    {
        if (r1 == r2)
        {
            st[parSegTree][node].ff = st[parSegTree][node].ss = value;
            return;
        }
        if (r1 != r2)
        {
            int leftChild = parSegTree << 1;
            int rightChild = leftChild | 1;
            st[parSegTree][node].ff = min(st[leftChild][node].ff, st[rightChild][node].ff);
            st[parSegTree][node].ss = max(st[leftChild][node].ss, st[rightChild][node].ss);
            return;
        }
    }
    int left = node << 1;
    int right = left | 1;
    int mid = (c1 + c2) >> 1;
    updateSegTreeIn_cx(parSegTree, r1, r2, left, c1, mid, y, value);
    updateSegTreeIn_cx(parSegTree, r1, r2, right, mid + 1, c2, y, value);
    st[parSegTree][node].ff = min(st[parSegTree][left].ff, st[parSegTree][right].ff);
    st[parSegTree][node].ss = max(st[parSegTree][left].ss, st[parSegTree][right].ss);
}
 
void updateSegTree(int node, int r1, int r2, int x, int y, ll value)
{
    if (r1 > r2 || r1 > x || r2 < x) return;
    if (r1 >= x && r2 <= x)
    {
        updateSegTreeIn_cx(node, r1, r2, 1, 1, col, y, value);
        return;
    }
    int left = node << 1;
    int right = left | 1;
    int mid = (r1 + r2) >> 1;
    updateSegTree(left, r1, mid, x, y, value);
    updateSegTree(right, mid+1, r2, x, y, value);
    updateSegTreeIn_cx(node, r1, r2, 1, 1, col, y, value);
}
 
void update(int x, int y, ll value)
{
    updateSegTree(1, 1, row, x, y, value);
}
 
int main()
{
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
 
    scanf("%d", &row);
    col = row;
    for (int i = 1; i <= row; i++) for (int j = 1; j <= col; j++) scanf("%lld", &grid[i][j]);
    gen2DSegTree();
    int q;
    scanf("%d", &q);
    while (q--)
    {
        char type[2];
        cin >> type;
        if (type[0] == 'q')
        {
            int r1, c1, r2, c2;
            scanf("%d %d %d %d", &r1, &c1, &r2, &c2);
            pll ans = query(r1, c1, r2, c2);
            printf("%lld %lld\n", ans.ss, ans.ff);
        }
        else
        {
            int r1, c1;
            ll value;
            scanf("%d %d %lld", &r1, &c1, &value);
            update(r1, c1, value);
        }
    }
}