Jon is the leader of killifish. Jon have a problem in these days. Jon has a plan to…
- User
Jon is the leader of killifish. Jon have a problem in these days. Jon has a plan to built new town in a pond. Of course new towns should have a school for children. But there are some natural enemies in a pond. Jon thinks that the place of a school should be the safest place in a pond for children.
Jon has asked by some construction companies to make construction plans and Jon has q construction plans now. The plan is selected by voting. But for each plan, the safest place for the school should be decided before voting.
A pond is expressed by a 2D grid whose size is r*c. The grid has r rows and c columns. The coordinate of the top-left cell is (0,0). The coordinate of the bottom-right cell is expressed as (r-1,c-1). Each cell has an integer which implies a dangerousness. The lower value implies safer than the higher value. q plans are given by four integer r1 ,c1 ,r2 and c2 which represent the subgrid. The top-left corner is (r1,c1) and the bottom-right corner is (r2,c2).
You have the r*c grid and q plans. Your task is to find the safest point for each plan. You should find the lowest value in the subgrid. Input
Input consists of multiple datasets. Each dataset is given in the following format.
r c q grid0,0 grid0,1 ... grid0,c-1 ... gridr-1,0 ... gridr-1,c-1 r1 c1 r2 c2 ... r1 c1 r2 c2
The first line consists of 3 integers, r ,c , and q . Next r lines have c integers. gridi,j means a dangerousness of the grid. And you can assume 0 ≤ gridi,j ≤ 231-1. After that, q queries, r1, c1, r2 and c2, are given.
The dataset satisfies following constraints. r*c ≤ 106 q ≤ 104 For each query, you can assume that r1≤ r2 and c1 ≤ c2 . If r * c ≤ 250000, q ≤ 100 is assured. If r * c > 250000, Input consists of only that case.
Output
For each query you should print the lowest value in the subgrid in a line.
Example
Input
3 3 4 1 2 3 4 2 2 2 1 1 0 0 2 2 0 0 1 1 1 0 1 0 0 1 1 2 1 10 4 1 2 3 4 5 6 7 8 9 10 0 0 0 9 0 0 0 4 0 5 0 9 0 4 0 5 0 0 0
Output
1 1 4 2 1 1 6 5
Assistant
We are given multiple datasets. Each dataset: r c q, then grid r x c, then q queries. For each query: r1 c1 r2 c2, find min over subgrid inclusive. Constraints: rc <= 1e6, q <= 1e4. Also, if rc <= 250000, then q <= 100; else input consists of only that case (meaning only one dataset with r*c > 250000). So overall memory for grid is up to 1e6 integers, which is fine.
We need to answer many range minimum queries (RMQ) over a 2D grid. Typically we could use 2D segment tree or Sparse Table for static grid. Since grid is static and queries are offline? Not necessarily, but we can preprocess. Since rc up to 1e6, building a 2D segment tree might be heavy: memory O(4 * r * c) ~ 4e6, which is acceptable. But query time O(log r * log c) ~ maybe up to log2(1000?) but r and c not bounded individually; could be up to 1e6 x 1? Actually rc <= 1e6, so dimensions could be 1e6x1 or 1000x1000. So we could build segment tree on rows and inside segment tree on columns; that's typical 2D segtree O(n*m) memory and O(log r * log c) query.
But we need to implement carefully, as it's a lot of recursion if we do segment tree of segment trees.
Alternatively, we could use a 2D sparse table for O(1) queries but memory O(rclog r*log c) which would be huge (1e6 * log1e6^2 ~ 1e6 * 400 ~ 400e6). Too large.
Alternatively, we could use a segment tree on rows, each node storing a 1D segment tree on columns? That's similar memory: O(r * 4 * c * 4) ~ 16 * n? Actually careful: typical 2D segment tree (tree of trees) uses O(4 * r * 4 * c) = O(16 * rc) ~ 16e6, still maybe acceptable memory (assuming 4 bytes per int -> 64 MB). However we need to store min, so ints. 16e6 ints = 64 MB. Might be okay but close to limit? But maybe we can compress using 2D segment tree with nodes storing arrays of size 4c? But there is a known implementation: Build segment tree over rows. For each node covering a range of rows, we build a segment tree over columns that stores the min of the rows in that node. Preprocess by merging rows: For leaf nodes (single row), the column segment tree is just the row values. For internal nodes, we combine the column segment trees of its children by taking min at each segment tree node. So memory is O(4r) for the row tree, each has a column tree of size O(4c). So total O(16 * r * c) worst-case. Since rc <= 1e6, that's up to 16 million nodes, each storing an integer. That's 64 MB, which is okay if memory limit is typical (512 MB). But careful: 16e6 ints = 64 MB. Additionally, recursion stack etc. But we need to manage multiple datasets? But if rc > 250000 then input consists of only that case, so only one dataset. So memory for one dataset should be fine.
But we also need to handle up to q=10000 queries, each O(log r * log c) time, say at most 20*20=400 operations, 4e6 operations, fine.
Implementation details: Since r and c vary, we need to implement a dynamic structure? Could implement as arrays for segment trees. However rc up to 1e6, but r and c may not be powers of two. Usually we can build segment tree with size = next power of two for convenience. For row tree: sizeR = 1; while sizeR < r: sizeR <<= 1; Then we allocate treeR = array of size 2sizeR, each element is a pointer to a column segment tree. For each node, we need to store a column tree. But we can't allocate a full column tree for each node using 4c memory if c is large but r small? The total memory would be O(sizeR * 4c) which could be larger than 16 * r * c if r is not a power of two? Actually sizeR <= 2r. So total memory O(2r * 4c) = 8 rc, but combined with internal nodes, it's more like O(4 * sizeR * 4c) = 16 * rc? Actually for each node in row segment tree (there are up to 2sizeR nodes) we store a column tree. 2sizeR <= 4r. So total column tree nodes = (4r) * (4c) = 16 rc. But that's the worst-case when we allocate full column trees for each row node. That's indeed O(16 rc). This is acceptable.
But we must be careful: If r=1 and c=1e6, then row tree sizeR=1 (or 2? Actually if we use 1-indexed tree, typical segment tree with size as power of two: sizeR=1; while sizeR < r: sizeR <<=1; For r=1, sizeR=1; then treeR array of length 2sizeR=2? Actually leaf at index sizeR (or sizeR+0). Usually we use array of size 2sizeR. But we only need to store column trees for nodes that exist; if we allocate column trees for all 2sizeR nodes, that's 2 nodes? That's fine. But we'd have to allocate column trees for each node; but if we allocate full column tree per node, that's okay. But in this case, r=1, c=1e6, then total column tree nodes: 2 * 4c = 8e6, which is 32 MB. Actually 4*c with c=1e6 is 4 million; times 2 = 8 million; each int 4 bytes = 32 MB. So memory okay.
But if r=1000, c=1000, then row nodes 4r=4000, each col tree 4c=4000 => 16e6 nodes = 64 MB. So that's okay.
We need to implement building: We'll precompute column trees for each row leaf: For leaf i (0-indexed) we set its col tree to the row values. For internal nodes, we combine two col trees by taking min of corresponding nodes.
We could represent column trees as arrays of ints. Since we have many column trees, we could store them in a contiguous memory block, but easier to allocate a vector for each node? That might cause many small allocations overhead. But we can use a single large array and assign offsets. Since we know total number of column tree nodes: For row tree node i, we need a column tree of size 4sizeC, where sizeC is next power of two >= c. So total nodes = (number of row tree nodes) * (4sizeC). The number of row tree nodes is 2sizeR, where sizeR = pow2 for rows. So total col nodes = 2sizeR * 4sizeC. That's <= 2 * (2r) * 4 * (2c) = 32 rc? Actually sizeR <= 2r (if r not power of two, but power of two just above r; worst-case sizeR = 2^ceil(log2(r)) < 2r). Similarly sizeC < 2c. So total nodes <= 2*(2r) * 4*(2c) = 32 r*c. That's double our previous estimate. Wait, let's compute precisely:
We have row segment tree with total number of nodes = 2 * sizeR. sizeR is the smallest power of two >= r. Since r>=1, sizeR < 2r (unless r is power of two exactly, then sizeR = r). Actually if r is a power of two, sizeR = r, then nodes = 2r. If r is not power of two, sizeR is the next power of two, which is > r and <= 2r. So nodes = 2sizeR <= 4r. The worst case when r=2^k+1, sizeR=2^{k+1} which is about 2r - 2? Actually if r = 2^{k} + 1, then sizeR = 2^{k+1} = 2(2^{k}) = 2*(r-1) approx 2r. So nodes = 2*sizeR <= 4r. So nodes <= 4r. Indeed.
Similarly column tree size: each column tree is a segment tree with 2sizeC nodes? Actually typical segment tree array implementation with size as power of two: we allocate tree array of size 2sizeC (if we use 1-indexed leaves at indices sizeC to 2sizeC-1). Or we can use 4sizeC (if we use recursive style). Usually for simplicity, we can use 4sizeC to cover the tree. But we can also use 2sizeC if we build like a perfect binary tree. But note that the typical segment tree for n elements uses 2N where N is power of two and we store values in leaves and internal nodes; the total nodes used is 2N-1, but if we use array of size 2N, index 1 is root, leaves from N to 2N-1. That's exactly 2N nodes. But careful: if we allocate 2sizeC, indices 1..2sizeC-1, we need sizeC >= c. The number of nodes is 2sizeC. So we could use 2sizeC. But if we use recursive segment tree building that allocates 4sizeC, it's safer and simpler but wastes memory. However we can optimize: Since we have to combine many column trees, we can use the 2sizeC representation. But the building process to combine trees: For leaf row node, we construct its column tree array (size 2sizeC) by setting leaves with row values, then building internal nodes upward. For internal row nodes, we combine two column trees: for each index i in the column tree, we take min of left and right's column tree at i. So we just need to store for each row node an array of size 2sizeC (or maybe 4sizeC). To minimize memory, we can use size 2sizeC, where we store leaves at indices sizeC to 2sizeC-1 (or 0-indexed). We'll decide representation.
Total memory: row node count * column tree size. row node count max 4r. column tree size = 2sizeC <= 4c. So total <= 4r * 4c = 16 rc. Actually 2sizeC <= 4c? Because sizeC < 2c, so 2sizeC < 4c. So 4r * 4c = 16 rc. So the earlier 16 rc is correct (if we use 2sizeC). But if we use 4sizeC, it's 4r * 8c = 32 rc. So better to use 2sizeC.
But we must consider that we need to handle queries on column tree: given a node covering rows [r1,r2], we query its column tree for column range [c1,c2]. For a column tree stored as array of size 2*sizeC, we can implement a recursive function that traverses the tree, but recursion depth log c. Or we can implement iterative segment tree query on the range. Since we have many queries, we might want to avoid recursion overhead by using iterative segment tree. But because we are calling it many times (each query does log r times column tree queries), we might just implement a recursive query function that is simple. The recursion depth is at most about 20 if c up to 1e6, so it's fine.
Let's plan:
For each dataset:
-
Read r, c, q.
-
Read grid: r rows, each row has c ints.
-
Compute sizeR = 1; while sizeR < r: sizeR <<= 1;
-
Compute sizeC = 1; while sizeC < c: sizeC <<= 1;
-
Allocate row tree: an array of vectors? Actually we need for each row node (index from 1 to 2sizeR-1 if we use 1-indexed, or 0-indexed). We'll allocate a 2D array: vector<vector> colTrees(2sizeR); but that would allocate many vectors and each vector of size 2sizeC. That's okay memory wise? But each vector has overhead; with 4r vectors (max 4e6? Actually rc <= 1e6, so r <= 1e6, c <= 1e6 but product limited, r could be 1e6, c=1. Then row node count = 4r = 4e6, and each vector of size 2sizeC = 21 =2, so total memory for vectors overhead would be huge: 4e6 vectors each has overhead (like pointer, size, capacity). That's unacceptable. So we cannot store a separate vector per row node when number of row nodes is large. But note: rc <= 1e6, so if r is large, c is small, and row node count is up to 4r which could be up to 4e6 (if r=1e6, c=1). That's 4 million row nodes. Storing a vector per node would be huge memory (each vector maybe 24 bytes plus allocated array). Even if we allocate a flat array for each node's column tree, we would need 4 million * (2sizeC) integers. But if c=1, sizeC=1, 2sizeC=2, that's 8 million integers ~ 32 MB. But plus overhead of storing pointers to arrays? If we allocate a separate array for each node using new int[2sizeC], we would have 4 million separate allocations which is terrible (memory overhead per allocation maybe 8 bytes). So better to allocate a single contiguous block of memory for all column trees. We can compute total elements: total_col_nodes = (2sizeR) * (2sizeC). Actually we need for each row node index from 0 to 2*sizeR-1 (if we use 0-indexed). We'll allocate a 1D array of length total_col_nodes. Then we can compute offset = node_id * col_size. This way we have a single big array and we can access column tree for node id by offset.
But careful: We need to build the column trees for each node. For leaf nodes corresponding to actual rows (i from 0 to r-1), we initialize their column tree leaves with the row values. For leaf nodes beyond r (if r < sizeR), we need to set them to a large value (infinity) so that they don't affect min. Or we can treat them as identity (INF). But since we query only within given r1..r2 which are within 0..r-1, we should be safe if we set out-of-range rows to INF; however in internal nodes, the min will be taken with INF, so it's fine. However when building the row tree, we need to combine children. So we can initialize all column trees for all nodes to INF or 0? We'll fill as we build.
We can build recursively: For each row node, we need its column tree. The standard approach: Build leaf row nodes (i from 0 to sizeR-1) by constructing their column tree from the row data if i < r else INF. Then for internal nodes from sizeR-1 down to 1, compute column tree as min of children's column trees element-wise.
But we need to allocate the big array.
Steps:
-
Compute sizeR = 1; while (sizeR < r) sizeR <<= 1; sizeC = 1; while (sizeC < c) sizeC <<= 1;
-
col_size = 2 * sizeC; // number of ints per column tree (using 1-indexed root at index 1? We'll decide indexing.)
Simplify: We'll use 0-indexed tree for columns: root at 0, left child 2i+1, right 2i+2, with leaves at indices from col_size/2? Actually typical segment tree with size as power of two: If we store in an array tree of length 2sizeC (with leaves from sizeC to 2sizeC-1), we can use 1-indexed or 0-indexed. Let's decide to use 0-indexed with root at 0? Actually the standard segment tree array for range minimum queries using iterative (non-recursive) approach is simpler: we can store values in an array of length 2sizeC, with leaves at indices sizeC to 2sizeC-1, and internal nodes from 1 to sizeC-1 (if 1-indexed). But then we can't easily combine trees element-wise because internal nodes correspond to specific indices. We can combine element-wise by iterating over all nodes from 1 to 2sizeC-1 (if 1-indexed). But if we use 0-indexed with tree stored in array of length 2sizeC, leaves at sizeC .. 2*sizeC-1, internal nodes at 1..sizeC-1 (if using 1-indexed) or 0..sizeC-1? Actually if we use 0-indexed for node indices, we could have root at 1? This is confusing.
Alternatively, we can use recursive segment tree building for columns, but we need to store the tree as an array for each row node. The easiest is to store the column tree as an array of size 4sizeC? But that would increase memory. However given that rc <= 1e6, memory for 4sizeC per row node might be too high if r is large and c is small? Actually if c is small, sizeC is small, 4sizeC is small. If r is large, number of row nodes is large but column tree size is small. So total memory is still O(rc * constant). Let's compute worst-case constant: Using 4sizeC per row node: row nodes up to 4r, column tree size up to 4sizeC <= 8c (since sizeC<2c, 4sizeC < 8c). So total <= 4r * 8c = 32 rc. That's double of using 2sizeC, but still okay (32e6 ints = 128 MB for rc=1e6). 128 MB might be borderline but probably acceptable if memory limit is high (512 MB). But we have to also store the grid maybe separate; but we can discard grid after building. So we can aim for a simpler implementation: Use 2sizeC representation (2*sizeC per row node) to be safe.
Implementing with 2sizeC representation: We'll use an array of length 2sizeC, where indices 0..sizeC-1 are internal nodes (maybe not used if we start leaves at sizeC). But typical segment tree with leaves at indices sizeC to 2sizeC-1 and internal nodes as parents. But to combine trees element-wise, we need to have corresponding indices for the same segment across trees. So if we store the tree in array where index i's children are 2i and 2i+1 (if we use 1-indexed root=1), then we can easily combine by iterating i from sizeC-1 down to 1 (for building). In that representation, total number of nodes is 2sizeC (indices 1..2sizeC). We can ignore index 0. So we allocate array of length 2sizeC (or 2sizeC+1 if 1-indexed). So col_size = 2sizeC. We'll use 1-indexed for easier child indexing: root at 1, left child = 2i, right = 2i+1. Leaves from sizeC to sizeC + c -1 hold actual values, and leaves beyond c (if c < sizeC) set to INF. Then internal nodes from sizeC-1 down to 1 store min of children.
For building leaf row nodes: we fill the leaf segment from offset + sizeC to offset+sizeC+c-1 with row values, set the rest to INF, then compute internal nodes by for i from sizeC-1 down to 1: tree[offset+i] = min(tree[offset+2i], tree[offset+2i+1]).
For internal row nodes: we combine two children's column trees: for i from 1 to 2sizeC-1 (or just all indices), the node's value = min(left_child_tree[i], right_child_tree[i]). But careful: The tree indices correspond to segments. Since the children column trees are stored similarly, we can simply iterate i from 1 to 2sizeC-1 and set parent_tree[offset_parent + i] = min( left_tree[offset_left + i], right_tree[offset_right + i] ). This works because the structure is identical. So we can do that.
Now for query: given row range [r1, r2] inclusive, and column range [c1, c2] inclusive, we need to compute min over subgrid. We'll query the row segment tree. Typically we traverse the row tree nodes covering the range [r1, r2] (using the iterative approach or recursion). For each such node, we query its column tree for column range [c1, c2] and take min of those results.
Thus we need a function query_col(tree_offset, c1, c2) that returns the min over columns in that column tree. We can implement recursive: function col_query(node, node_l, node_r) that checks if range overlaps, etc. Since we have many queries, recursion depth is small, fine. But we need to know the node's segment boundaries; we can compute them based on node index and the sizeC. Since we are using a segment tree with leaves representing individual columns 0..sizeC-1? Actually leaves correspond to columns 0..sizeC-1. But c might be less than sizeC; columns beyond c-1 are INF. Query range [c1, c2] is within 0..c-1. So we can query only relevant leaves. Use recursion starting at root (index=1) with range [0, sizeC-1]. But we can optimize by using iterative segment tree query: typical method for static segment tree with power-of-two size: convert to half-open intervals: leaf for column j is at index sizeC + j. Then to query [c1, c2], we can do l = c1 + sizeC, r = c2 + sizeC + 1 (if we use half-open). Then we traverse up while l < r, taking min of values when l is odd etc. That's efficient and non-recursive. However this works for a single segment tree that stores min and is built over an array of length sizeC (with INF for extra). Let's recall: For segment tree with leaves stored at index i+sizeC, we have tree of length 2*sizeC. For query on range [l, r] inclusive, we can convert to half-open [l, r+1). Then we do:
l += sizeC; r += sizeC + 1; // because we want r exclusive min_val = INF; while (l < r) { if (l & 1) min_val = min(min_val, tree[l++]); if (r & 1) min_val = min(min_val, tree[--r]); l >>= 1; r >>= 1; } return min_val;
This works if tree array is 0-indexed with leaves at indices sizeC .. 2sizeC-1. But note that we are using 1-indexed representation? Let's decide: we want to combine trees element-wise easily; if we use 0-indexed, internal nodes indices don't align to 2i and 2i+1 nicely? Actually they do: 0-indexed: children of i are 2i+1 and 2i+2. That is different from 1-indexed. For element-wise combination, it's easier if we have same indexing across trees. Either indexing works as long as consistent. For simplicity, we could use 0-indexed with root at 0, left child = 2i+1, right = 2i+2. Then total nodes = 2sizeC - 1? Actually for a full binary tree with sizeC leaves (power of two), number of nodes is 2sizeC - 1 if we use 0-indexed compact array where root=0 and leaves start at some index. But we want to allocate exactly 2sizeC nodes to have a simple offset scheme. Usually we allocate an array of size 2sizeC, where leaves are at indices sizeC to 2sizeC-1, and internal nodes are at 1..sizeC-1 (1-indexed). If we use 0-indexed for array, we can still use indices 1..2sizeC-1 for nodes, ignoring index 0, then root is 1. That's easier: we allocate array of length 2sizeC (or 2sizeC+5) and use 1-indexing. For leaves: index = sizeC + j (0 <= j < sizeC). So leaf for column j is at idx = sizeC + j. Then internal nodes: children: left = 2i, right=2*i+1.
To query iterative: we can adapt to 1-indexed: set l = c1 + sizeC, r = c2 + sizeC. But typical iterative range query works for half-open intervals if we store leaves in an array and use l and r as exclusive. Let's adopt standard approach for 1-indexed:
Let N = sizeC. We have tree[1..2N-1]? Actually we have 2N nodes if we include index 0? Usually we use tree of size 2N, with indices from 0 to 2N-1, and leaves at N..2*N-1. In 0-indexed, root at 1? Let's define:
We allocate array
tof length 2sizeC. We will use indices 0..2sizeC-1, but we will treat index 1 as root? That's messy. Better to use typical segment tree representation: tree = vector(2sizeC). We'll use 0-indexed where leaves are at index sizeC + i (i from 0). And internal nodes are at indices 1..sizeC-1? Actually if we allocate 2sizeC elements, indices 0..2*sizeC-1, we can assign:- For i in [0, sizeC-1]: internal nodes? There's no simple mapping. Standard segment tree with power of two size uses tree[1..2sizeC] or tree[0..2sizeC-1] with 1-indexing being common. Many competitive programmers use an array of size 4*n, but that's recursive. For iterative query, they use:
int n = sizeC; vector t(2n); // build: for i=0..c-1: t[n+i] = row[i]; for i=n-1; i>=1; i--) t[i] = min(t[2i], t[2i+1]); // But note that t[0] is unused if we start at 1. Actually if we use t of size 2n, we can index from 1 to 2n-1. But then we need to allocate 2n+1 to use 1-index. Let's allocate tree of size 2sizeC (maybe 2sizeC+2) and use indices 1..2sizeC. Then leaves at indices sizeC .. 2sizeC. This is simpler for combination: root =1, left child = 2i, right=2i+1. Leaves: index = sizeC + j, for j in [0, sizeC-1]. Then total nodes = 2sizeC, because indices from 1 to 2sizeC inclusive? Actually if we have sizeC leaves, we need 2sizeC nodes if we include root at 1 and leaves up to 2sizeC. For example, sizeC=1: we need 1 leaf and root? Actually with sizeC=1, tree: root is also leaf. If we use representation: leaf at index 1? But we want uniformity: Usually we allocate tree of size 2sizeC, and set leaves at indices sizeC to 2sizeC-1 (0-indexed) or sizeC to 2*sizeC-1? Let's check.
I recall typical iterative segment tree implementation (from CP handbook) uses:
int n = 1; while (n < N) n = 2; vector tree(2n); // build: for i=0; i<N; i++) tree[n+i] = array[i]; // for i=n-1; i>=1; i--) tree[i] = combine(tree[2i], tree[2i+1]); // Here tree[0] is unused, indices 1..2n-1? Actually they use tree[0..2n-1], but they start from 1. They set tree[0] as unused. So they allocate 2n, and use indices 1..2n-1? Let's test: if n=2, allocate tree size 4? Actually 2*n =4, indices 0,1,2,3. They set tree[2] and tree[3] as leaves (n=2, so n+i for i=0,1 gives indices 2,3). Then they compute for i=n-1=1 down to 1: tree[1] = combine(tree[2], tree[3]). So tree[0] is unused. So total used nodes: indices 1,2,3 -> 3 nodes. But the array size is 4. So we have extra slot at index 0. This is fine. For query they use l = n + left, r = n + right+1, while l < r... This works with tree indices.
So in this representation, we have indices from 1 to 2n-1 used, with n leaves at indices n..2n-1. So total nodes = 2n - 1, but array size is 2n (including index 0). So to combine element-wise across trees, we need to ensure that for each node we have a corresponding index. Since we have 2n indices allocated but index 0 unused, we can ignore it. But when we combine trees, we want to iterate over indices 1 to 2n-1. That's fine. Also for leaves beyond c, we set tree[n+i] = INF for i >= c.
Thus we can allocate col_size = 2 * sizeC (i.e., number of elements, but we will use indices 1..2sizeC-1). Actually we need array length = 2sizeC. We'll use indices 1..2sizeC-1 for nodes. So the number of used nodes is 2sizeC -1, but we might store them in an array of length 2sizeC, and we can ignore index 0. For each row node, we need to store that array of length 2sizeC, but we can store it as length 2sizeC and use indices 0..2sizeC-1, but we just use indices 1..2sizeC-1. For convenience, we will allocate length = col_size = 2sizeC, and store from index 0 (unused) and indices 1..col_size-1 (since col_size-1 = 2sizeC-1). So memory per column tree = 2sizeC integers. That's perfect.
Thus total memory = (2sizeR) * (2sizeC) integers, but we can actually allocate only for used nodes? Actually number of row nodes used in segment tree is 2sizeR (including index 0 unused). In typical iterative segment tree for rows, we also might use 2sizeR array for row tree. But we are building a full segment tree over rows, not iterative queries; we need to store column trees for each node in the row segment tree. We'll allocate an array of size (2sizeR) * (2sizeC) ints. However, row segment tree internal nodes: we need to store column tree for each node index from 1 to 2sizeR-1? But we also need to handle indexing similar to column tree: we can allocate row nodes from index 1 to 2sizeR-1 (since we might use 1-indexing for rows as well). That gives total row nodes = 2sizeR - 1. But we also might have leaves at indices sizeR to sizeR + r -1, etc. We can adopt the same representation: use array rowsTree of length 2sizeR, where index 1 is root, leaves at indices sizeR .. sizeR+r-1 (with out-of-range leaves set to INF). Then we need to store column trees for each index 1..2sizeR-1 (since index 0 unused). So number of row nodes = 2sizeR - 1. But we can allocate an array of size (2sizeR) * (2sizeC) and use row_offset = row_idx * col_size, but row_idx ranges from 0 to 2sizeR (maybe inclusive)? We'll allocate exactly (2sizeR) * col_size, and we'll map row_idx (1..2sizeR-1) to offset = row_idx * col_size. But then we need to also allocate for index 0? We'll just allocate for 2sizeR elements, but if we start at index 1, we need offset for index 1 = 1col_size. So we need array of size (2sizeR) * col_size, and we will use indices 1..2*sizeR-1. So we waste first col_size entries for index 0. That's okay.
Alternatively, we can allocate a vector
vector<int> big( (2*sizeR) * col_size )and then access via big[row_idx * col_size + node_in_col] where row_idx in [0, 2sizeR-1]? But then we need to compute offset based on row_idx. If we use row_idx from 0 to 2sizeR-1, we can use indices 0..2sizeR-1. But then we need to map the row segment tree node indices to 0..2sizeR-1. In typical iterative segment tree, we have nodes 0..2*sizeR-1? Let's define clearly.Simpler: We'll build the row segment tree recursively. We can avoid the iterative row tree and use recursive building. For recursive building, we can assign an id to each node we create, and store column tree in a contiguous array per node. However, we would need to know the mapping from node to offset. If we use a recursive segment tree over rows, we can allocate nodes dynamically as objects with left/right children and a vector for column tree. That might be simpler but memory overhead for pointers is high. Better to use iterative (bottom-up) building for rows as well, similar to column trees. That would allow us to use simple indexing.
So we will treat the row segment tree as a segment tree built on an array of rows. The segment tree will have leaves corresponding to rows 0..sizeR-1, with actual rows in first r leaves, and the rest filled with INF column trees. Then we build internal nodes by combining children column trees element-wise.
Thus we need:
- sizeR = power of two >= r.
- total_row_nodes = 2 * sizeR (including index 0 unused). Actually we will use array of length 2sizeR for row node indices (1-indexed). But for column tree storage, we need an array of length total_row_nodes * col_size, where total_row_nodes = 2sizeR (to have index up to 2sizeR-1). Let's decide to index row nodes from 0 to 2sizeR-1, but we'll use 1-indexing for simplicity of combining children: For node i (1-indexed), left child = 2i, right = 2i+1. If we use 0-indexed row nodes, then children are 2i+1 and 2i+2, but then the root is 0. But then the total number of nodes for a full binary tree with sizeR leaves is 2sizeR - 1 if we use 0-indexed compact? Actually for a full binary tree with n leaves (power of two), the number of nodes is 2n - 1. If we store in an array of size 2n, and index from 1, we have nodes 1..2n-1. If we index from 0, we could store nodes 0..2*n-2? That's messy. I'd prefer 1-indexed for both row and column trees to keep child indices simple.
Thus:
- Let R = sizeR, C = sizeC.
- Let col_sz = 2 * C (we will use indices 1..2*C-1, index 0 unused). So memory per column tree = col_sz integers.
- Let row_sz = 2 * R (we will use indices 1..2R-1, index 0 unused). So number of row nodes = 2R - 1, but we allocate array of size row_sz * col_sz, and we will use row indices from 1 to 2*R-1. We'll ignore row index 0.
Now we need to fill column trees for leaf row nodes (i from R to R+r-1) with actual row values. For leaf rows beyond r-1 (i from R+r to 2*R-1) we set column tree leaves to INF and internal nodes accordingly.
But note: Leaves for row tree are indices from R to 2R-1. For i in [R, R+r-1], it corresponds to actual row (i - R). For i in [R+r, 2R-1], they are extra leaves.
We need to build column trees for leaves: For each leaf node i (row node index), we need to set its column tree. We'll have a function build_leaf(i, row_data) that fills the column tree at offset = i * col_sz.
Since we are using a 1D flat array
bigof length (2R) * col_sz (maybe we allocate size (2R) * col_sz). We'll compute offset = i * col_sz. Then we fill the column tree array at positions offset+1 to offset+col_sz-1 (since we ignore index 0). But careful: The column tree array for node i is stored from offset to offset+col_sz-1 inclusive. Since we want to use index 1..col_sz-1, we need to access big[offset + j] for j from 1 to col_sz-1. So we can treat big as base pointer, and for node i, the column tree arraytreecan be accessed asbig + offset, with tree[0] unused. So we need to allocate big with size (2*R) * col_sz, and we will computebase = i * col_sz.Now building leaf: For leaf node i corresponding to actual row
row_idx = i - R(if i < R+r). For that leaf, we need to set leaf values in column tree: for column j from 0 to c-1, set big[offset + C + j] = grid[row_idx][j]. For columns j from c to C-1, set big[offset + C + j] = INF (since they are beyond actual columns). Then for internal nodes of column tree, we compute from C-1 down to 1: big[offset + k] = min(big[offset + 2k], big[offset + 2k+1]).But note: Since we use 1-indexed, the indices for leaves are C+0, C+1, ..., C+C-1. That is total of C leaves. So we need to set leaves for j from 0 to C-1. For j >= c, set INF.
Now for leaf rows that are beyond actual rows (i >= R+r), we set all leaves to INF and compute internal nodes similarly.
After all leaves built, we need to build internal row nodes (i from R-1 down to 1). For each internal node i, we combine its left child's column tree (node 2i) and right child's column tree (node 2i+1). That is, for each column tree index j from 1 to 2C-1, we set big[icol_sz + j] = min(big[(2i)col_sz + j], big[(2i+1)col_sz + j]). That's O(C) per internal node, which would be O(RC) = O(sizeR * sizeC) which could be up to 4rc (since sizeR < 2r, sizeC < 2c) so 4 * r * c? Actually RC <= (2r)(2c) = 4 rc. So building all internal nodes by iterating over all column tree indices for each internal row node leads to O(RC * something) = O(rc * 4 * (2R?) Actually number of internal row nodes is about R-1, so total operations = (R-1) * (2C) ~ 2RC = O(8 rc) maybe? Since R <= 2r, C <= 2c, product <= 4 rc, multiplied by 2 = 8 rc, which is about 8e6 operations, acceptable. However building leaf nodes also requires O(RC) since we fill each leaf's column tree. So total building O(RC) which is at most 4rc? Actually leaves: there are R leaves (since we have R leaf row nodes, not 2R). So building leaves: R * O(C) = RC <= 2r * 2c = 4 rc. So total building O(8 rc). With rc <= 1e6, that's fine.
Now queries: For each query (r1,c1,r2,c2) inclusive. We need to compute min over rows r1..r2 and cols c1..c2.
We can query row tree recursively or iteratively. Since row tree is built as segment tree, we can write a recursive function that takes node index, node row interval [l, r] (in terms of leaf rows 0..R-1) and queries it. But we might want to avoid recursion due to many queries? But recursion depth is log2(R) <= 20 (since R <= 2r <= 2e6, log2(2e6)~21). That's fine. But we need to query many times, recursion overhead minimal.
Alternatively, we can do iterative row query similar to segment tree: we convert row range to half-open [r1, r2+1) and then process nodes in the row tree with an iterative method, but that method returns the min over a set of nodes by combining their column tree query results. For each node that fully covers a segment of rows, we query its column tree for columns [c1, c2] and take min with current answer. So we need to traverse the row tree nodes that exactly cover the row range. Using iterative segment tree (like in 1D) we can get those nodes quickly. Let's adopt iterative method.
We'll use the row segment tree similar to column tree: leaves at indices R + r (for r from 0..R-1). We'll store column trees for each node. To query row range [r1, r2] inclusive, we do:
l = r1 + R r = r2 + R + 1 (converted to half-open) ans = INF while (l < r) { if (l & 1) { ans = min(ans, query_col(tree_of_node[l], c1, c2)); l++; } if (r & 1) { r--; ans = min(ans, query_col(tree_of_node[r], c1, c2)); } l >>= 1; r >>= 1; } return ans;
But careful: The node indices in row tree: leaves are at indices R + i for i in [0, R-1]. The internal nodes are 1..R-1. The iterative query works if the tree is built over array of size R (power of two) with leaves at indices R..2R-1. That's exactly our representation if we have row nodes from 1..2R-1, with leaves at R..2R-1. So we can use this method.
Now we need a function query_col(node_offset, c1, c2) that queries the column tree stored at offset = node_idx * col_sz. Since we have the column tree built with leaves at C..2C-1, we can do iterative query similarly:
int query_col(int offset, int c1, int c2) { int l = c1 + C; int r = c2 + C + 1; int res = INF; while (l < r) { if (l & 1) { res = min(res, big[offset + l]); l++; } if (r & 1) { r--; res = min(res, big[offset + r]); } l >>= 1; r >>= 1; } return res; }
But note: In the column tree, the array indices we stored are from offset+1 to offset+col_sz-1 (since we allocated col_sz = 2C). Leaves are at indices C..2C-1. So the indexing matches: offset + l, offset + r, where l and r are in [C, 2C-1] and internal nodes as we traverse up. This works because we built the tree in the same way: we used indices 1..2C-1, but we stored values at those indices. In the iterative query algorithm, we need to start from indices l = c1 + C, r = c2 + C + 1, which are within C..2C. The algorithm accesses tree[l] and tree[r] (where tree is the array). It assumes the root is index 1, but the algorithm only uses indices that are within 1..2C-1? Actually when we set l = c1 + C, we might have l == 2C? For c2 = C-1, then r = (C-1) + C + 1 = 2C. That's index 2C, which is beyond our allocated range if we only have indices up to 2C-1. In typical iterative segment tree, the array size is 2C, and we use indices from 1 to 2C-1 (since index 0 unused). The leaf indices are from C to 2C-1 inclusive. When we set r = c2 + C + 1, it may become 2C (when c2 = C-1). However, in the loop, we check if (r & 1) before decrementing r? Actually the standard loop:
int l = left + n, r = right + n; int res = INF; while (l < r) { if (l & 1) res = min(res, tree[l++]); if (r & 1) res = min(res, tree[--r]); l >>= 1; r >>= 1; }
Here
leftis inclusive,rightis exclusive? Usually it's for range [l, r) where leaves cover indices 0..n-1. In many implementations, they set l = left + n, r = right + n, and then loop. That's for half-open interval. If we want inclusive [c1, c2], we can set l = c1 + C, r = c2 + C + 1. Then r can be up to C + (C-1) + 1 = 2C. But we only have tree indices up to 2C-1. However, note that in the loop, when we check if (r & 1), we decrement r first: tree[--r]. If r is 2C, then --r = 2C-1, which is valid. So it's okay that r is initially 2C because we decrement before accessing. So we need the array to have index up to 2C-1. So we allocate col_sz = 2C. But we are not using index 0. So array indices we use are from 1 to col_sz-1 (since col_sz = 2C, so max index is 2C-1). That's fine. So we can compute offset + idx where idx ranges from 1 to 2C-1. In the loop, l starts at c1+C, which is between C and 2C-1 (since c1 <= C-1). r starts at c2+C+1, which is between C+1 and 2C. When r is 2C, we decrement to 2C-1 before accessing, so idx is valid. However we also access l as is before increment. l is always <= 2*C-1. So it's fine.But note: we are using big[offset + l] where l might be 2C? Actually if r = 2C, we don't access big[offset + r] before decrement. We check if (r & 1) and then do --r and access. So r is not used as index before decrement. So no problem. So our column tree array needs to have indices up to offset + (2C-1). Since we allocate col_sz = 2C per node, indices from offset to offset+col_sz-1 inclusive. That includes offset+2*C-1 as last valid. So fine.
Thus query_col works.
Now for row query: we need to get the column tree of a row node using its offset. The offset for row node idx is idx * col_sz. But careful: We allocated big of size (2R) * col_sz. So row node indices range from 0 to 2R-1? But we intend to use indices 1..2R-1. So we should compute offset = idx * col_sz. However if idx = 2R-1, offset = (2R-1)col_sz. That is within allocated size if we allocated (2R)col_sz because max idx = 2R-1, offset max = (2R-1)col_sz < 2R*col_sz, so valid. For idx=0 we don't use. So we can compute offset = idx * col_sz.
But we need to be careful about integer overflow: row nodes up to 2R, R <= 2max(r) but rc <= 1e6, so R <= 21e6? Actually r <= 1e6, c <= 1e6 but product <= 1e6, so if r=1e6, c=1, then R is next power of two >= r = 2^20 = 1048576? Actually 1e6 ~ 2^20 (1,048,576). So R could be up to 2^20 = 1,048,576. Then 2R = 2,097,152. So idx up to ~2 million. col_sz = 2C, with c=1, C=1, col_sz=2. So total big size = 2,097,152 * 2 = ~4.2 million ints = 16 MB. Fine. If r=1000, c=1000, R ~ 1024, C ~ 1024, col_sz=2048, big size = (21024=2048) * 2048 = 4,194,304 ints = 16 MB. Actually 20482048=4,194,304 ~ 4.2 million ints = 16.8 MB. If r=1000, c=1000, product=1e6, so fits. If r=500, c=2000, product=1e6, R=512, C=2048, col_sz=4096, big size = (2512=1024) * 4096 = 4,194,304 again ~ 4.2 million ints. So memory is about 4 million ints in many cases? Wait compute: 2R * 2C = 4 * R * C. Since R <= 2r, C <= 2c, then 4 * R * C <= 4 * (2r)(2c) = 16 rc. So memory is at most 16 * rc integers. With r*c <= 1e6, max 16e6 ints = 64 MB. That's acceptable.
But we need to also store the grid itself temporarily. We can read grid into a 2D vector and then discard after building? We need to build leaves, so we need the grid values. After building we can free grid, but in C++ we can just use vector and let it go out of scope. But we might keep grid until building done. That's okay.
Now building process:
Given grid as vector<vector> (r rows, each with c ints). We'll compute R, C.
Allocate big vector of ints: vector big( (2*R) * col_sz, INF ). We'll fill with INF initially.
Set INF = something like INT_MAX or 2^31-1? Since grid values are up to 2^31-1, we can use 2^31-1 as INF or use LLONG_MAX? But min operation; we can use INT_MAX (which is 2^31-1). Since values are within that range,
-