/*
Problem link
Type: Data Structure - 2D Segment tree/Quad tree.
- Build a max and min 2D segment tree.
- 2D segment tree contains 4 child nodes at each node.
- Each node represents a sub-region in a 2D array.
- A sub-region is divided into 4 equal sub-regions, each is represented by the child node.
*/
#include <iostream>
#include <cmath>
#include <vector>
#include <ctime>
#include <cstring>
using namespace std;
#define oo (1 << 30)
class SegmentTree_2D {
protected:
struct Node {
// Position of the max value in node.
int x, y;
// Max value of this node.
int value;
Node(int xx, int yy, int val) : x(xx), y(yy), value(val) {}
Node() {};
bool operator < (const Node &otherNode) {
return this->value < otherNode.value;
}
bool operator > (const Node &otherNode) {
return this->value > otherNode.value;
}
};
private:
vector<Node> nodes;
int size;
int n,m;
public:
SegmentTree_2D(int n, int m) {
nodes = vector<Node>(1 + 2 * n * m);
this->n = n;
this->m = m;
}
SegmentTree_2D() {
this->n = 0;
this->m = 0;
}
void buildFromArray(int **array) {
build(1, 0, 0, n - 1, m - 1, array);
}
void updateValueAtCell(int row, int col, int value) {
update(1, row, col, value, 0, 0, n - 1, m - 1);
}
int queryValueInRange(int x1, int y1, int x2, int y2) {
Node maxNode = query(1, x1, y1, x2, y2, 0, 0, n - 1, m - 1);
return maxNode.value;
}
private:
Node build(int index, int a1, int b1, int a2, int b2, int **array) {
if (a1 > a2 || b1 > b2) {
return def();
}
if (a1 == a2 && b1 == b2) {
return nodes[index] = Node(a1, b1, array[a1][b1]);
}
Node child_1 = build(index * 4 - 2, a1, b1, (a1 + a2) / 2, (b1 + b2) / 2, array);
Node child_2 = build(index * 4 - 1, (a1 + a2) / 2 + 1, b1, a2, (b1 + b2) / 2, array);
Node child_3 = build(index * 4, a1, (b1 + b2) / 2 + 1, (a1 + a2) / 2, b2, array);
Node child_4 = build(index * 4 + 1, (a1 + a2) / 2 + 1, (b1 + b2) / 2 + 1, a2, b2, array);
Node maxValue = def();
maxValue = this->max(maxValue, child_1);
maxValue = this->max(maxValue, child_2);
maxValue = this->max(maxValue, child_3);
maxValue = this->max(maxValue, child_4);
return nodes[index] = maxValue;
}
Node update(int index, int row, int col, int value, int a1, int b1, int a2, int b2) {
if (a1 > a2 || b1 > b2) {
return def();
}
if (a1 == row && b1 == col && a1 == a2 && b1 == b2) {
return nodes[index] = Node(a1, b1, value);
}
if (a1 > row || a2 < row || b1 > col || b2 < col) {
return nodes[index];
}
Node maxNode = def();
Node child_1 = update(index * 4 - 2, row, col, value, a1, b1, (a1 + a2) / 2, (b1 + b2) / 2);
Node child_2 = update(index * 4 - 1, row, col, value, (a1 + a2) / 2 + 1, b1, a2, (b1 + b2) / 2);
Node child_3 = update(index * 4, row, col, value, a1, (b1 + b2) / 2 + 1, (a1 + a2) / 2, b2);
Node child_4 =
update(index * 4 + 1, row, col, value, (a1 + a2) / 2 + 1, (b1 + b2) / 2 + 1, a2, b2);
maxNode = this->max(maxNode, child_1);
maxNode = this->max(maxNode, child_2);
maxNode = this->max(maxNode, child_3);
maxNode = this->max(maxNode, child_4);
return nodes[index] = maxNode;
}
Node query(int index, int x1, int y1, int x2, int y2, int a1, int b1, int a2, int b2) {
if (a1 > a2 || b1 > b2) {
return def();
}
if (x2 < a1 || x1 > a2 || y2 < b1 || y1 > b2) {
return def();
}
if (x1 <= a1 && x2 >= a2 && y1 <= b1 && y2 >= b2) {
return nodes[index];
}
Node maxNode = def();
Node child_1 = query(index * 4 - 2, x1, y1, x2, y2, a1, b1, (a1 + a2) / 2, (b1 + b2) / 2);
Node child_2 = query(index * 4 - 1, x1, y1, x2, y2, (a1 + a2) / 2 + 1, b1, a2, (b1 + b2) / 2);
Node child_3 = query(index * 4, x1, y1, x2, y2, a1, (b1 + b2) / 2 + 1, (a1 + a2) / 2, b2);
Node child_4 =
query(index * 4 + 1, x1, y1, x2, y2, (a1 + a2) / 2 + 1, (b1 + b2) / 2 + 1, a2, b2);
maxNode = this->max(maxNode, child_1);
maxNode = this->max(maxNode, child_2);
maxNode = this->max(maxNode, child_3);
maxNode = this->max(maxNode, child_4);
return maxNode;
}
// Virtual definition of an INF node.
virtual Node def() = 0;
// Virtual method to get the max of 2 nodes.
virtual Node max(Node a, Node b) = 0;
};
// Subclass SegmentTree_2D to implement max() and def() methods.
class Max_SegmentTree_2D : public SegmentTree_2D {
public:
Max_SegmentTree_2D(int n, int m) : SegmentTree_2D(n, m) {}
Max_SegmentTree_2D() : SegmentTree_2D() {}
private:
Node max(Node a, Node b) {
if (a.value > b.value) {
return a;
} else {
return b;
}
}
Node def() {
return Node(0, 0 , -oo);
}
};
class Min_SegmentTree_2D : public SegmentTree_2D {
public:
Min_SegmentTree_2D(int n, int m) : SegmentTree_2D(n ,m) {}
Min_SegmentTree_2D() : SegmentTree_2D() {}
private:
Node max(Node a, Node b) {
if (a.value < b.value) {
return a;
} else {
return b;
}
}
Node def() {
return Node(0, 0, oo);
}
};
const char* fi = "input.txt";
// Use pointer to pointer for 2D array.
int **a;
int n, q;
Max_SegmentTree_2D maxTree;
Min_SegmentTree_2D minTree;
void readArray();
void release();
void testGenerator();
int main(int argc, const char * argv[]) {
readArray();
cin >> q;
for (int i = 0; i < q; i++) {
char type;
cin >> type;
if (type == 'q') {
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
cout << maxTree.queryValueInRange(x1 - 1, y1 - 1, x2 - 1, y2 - 1) << " "
<< minTree.queryValueInRange(x1 - 1, y1 - 1, x2 - 1, y2 - 1) << endl;
} else if (type == 'c') {
int x, y, value;
cin >> x >> y >> value;
maxTree.updateValueAtCell(x - 1, y - 1, value);
minTree.updateValueAtCell(x - 1, y - 1, value);
}
}
release();
return 0;
}
void readArray() {
cin >> n;
a = new int* [n];
for (int i = 0; i < n; i++) {
a[i] = new int[n];
for (int j = 0; j < n; j++) {
cin >> a[i][j];
}
}
maxTree = Max_SegmentTree_2D(n, n);
maxTree.buildFromArray(a);
minTree = Min_SegmentTree_2D(n, n);
minTree.buildFromArray(a);
}
void release() {
for (int i = 0; i < n; i++) {
delete[] a[i];
}
delete[] a;
}
void testGenerator() {
int nn = 500;
srand(time(NULL));
cout << nn << endl;
for (int i = 0; i < nn; i++) {
for (int j = 0; j < nn; j++) {
cout << rand()%10000 << " ";
}
cout << endl;
}
int qq = 40000;
cout << qq << endl;
for (int i = 0; i < qq; i++) {
int option = rand()%2;
switch (option) {
case 0: {
int x1 = rand()%nn + 1;
int y1 = rand()%nn + 1;
int x2, y2;
while (true) {
x2 = rand()%nn + x1;
if (x2 < nn && x2 > x1) break;
}
while (true) {
y2 = rand()%nn + y1;
if (y2 < nn && y2 > y1) break;
}
cout << 'q' << " " << x1 << " " << y1 << " " << x2 << " " << y2 << endl;
break;
}
case 1: {
int x = rand()%nn + 1;
int y = rand()%nn + 1;
int value = rand()%10000;
cout << 'c' << x << " " << y << " " << value << endl;
break;
}
}
}
}
No comments:
Post a Comment