| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1248420 | mazen_ghanayem | 게임 (IOI13_game) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include "game.h"
using namespace std;
// Define long long for convenience
#define int long long
/**
* @struct DynamicSegTree2D
* @brief Implements a 2D Dynamic Segment Tree.
*
* This data structure is useful for performing 2D range queries (e.g., sum, min, max)
* and point updates on a very large or sparse 2D grid. It avoids allocating
* memory for the entire grid by creating nodes only when they are needed.
*
* The structure is essentially a dynamic segment tree of dynamic segment trees.
* The "outer" or "x-tree" segments the rows (first dimension), and each of its nodes
* contains a pointer to another "inner" or "y-tree" that segments the columns
* (second dimension) for that row range.
*
* @tparam T The data type of the values stored in the tree.
* @tparam M The merge operation function (e.g., plus, minimum, maximum).
*/
struct DynamicSegTree2D {
// The default value for nodes that don't exist and for query results on empty ranges.
int DEFAULT_VALUE;
/**
* @brief Merges two values. This is the core operation of the segment tree.
* @param a The first value.
* @param b The second value.
* @return The result of merging a and b.
*/
int merge(int a, int b) {
return a + b; // Example: sum. Can be changed to min(a,b), max(a,b), etc.
}
// --- Inner Segment Tree (for columns/y-axis) ---
struct NodeY {
int val;
NodeY *left = nullptr, *right = nullptr;
NodeY(int v = 0) : val(v) {}
// Safely get value from a node, returning default if null
int left_val() { return left ? left->val : 0; }
int right_val() { return right ? right->val : 0; }
};
// --- Outer Segment Tree (for rows/x-axis) ---
struct NodeX {
NodeY* y_tree = nullptr; // Pointer to the root of the column segment tree
NodeX *left = nullptr, *right = nullptr;
};
NodeX* root;
int min_x, max_x, min_y, max_y;
/**
* @brief Constructor for the 2D Dynamic Segment Tree.
* @param min_coord_x The minimum possible x-coordinate.
* @param max_coord_x The maximum possible x-coordinate.
* @param min_coord_y The minimum possible y-coordinate.
* @param max_coord_y The maximum possible y-coordinate.
*/
DynamicSegTree2D(int min_coord_x, int max_coord_x, int min_coord_y, int max_coord_y)
: min_x(min_coord_x), max_x(max_coord_x), min_y(min_coord_y), max_y(max_coord_y) {
root = new NodeX();
DEFAULT_VALUE = 0;
}
DynamicSegTree2D(){}
// --- Update Functions ---
/**
* @brief Updates the value in the inner y-tree (columns).
*/
void update_y(NodeY*& node, int y, int val, int cur_min_y, int cur_max_y) {
if (!node) {
node = new NodeY();
}
if (cur_min_y == cur_max_y) {
node->val += val; // Update the value at the target y-coordinate
return;
}
int mid_y = cur_min_y + (cur_max_y - cur_min_y) / 2;
if (y <= mid_y) {
update_y(node->left, y, val, cur_min_y, mid_y);
} else {
update_y(node->right, y, val, mid_y + 1, cur_max_y);
}
node->val = merge(node->left_val(), node->right_val());
}
/**
* @brief Updates the value in the outer x-tree (rows), propagating to the y-trees.
*/
void update_x(NodeX*& node, int x, int y, int val, int cur_min_x, int cur_max_x) {
if (!node) {
node = new NodeX();
}
// Update the corresponding y-tree at this x-node
update_y(node->y_tree, y, val, min_y, max_y);
if (cur_min_x == cur_max_x) {
return;
}
int mid_x = cur_min_x + (cur_max_x - cur_min_x) / 2;
if (x <= mid_x) {
update_x(node->left, x, y, val, cur_min_x, mid_x);
} else {
update_x(node->right, x, y, val, mid_x + 1, cur_max_x);
}
}
/**
* @brief Public interface for updating a value at a specific (x, y) coordinate.
* @param x The x-coordinate.
* @param y The y-coordinate.
* @param val The value to add.
*/
void update(int x, int y, int val) {
update_x(root, x, y, val, min_x, max_x);
}
// --- Query Functions ---
/**
* @brief Performs a range query on the inner y-tree (columns).
*/
int query_y(NodeY* node, int y1, int y2, int cur_min_y, int cur_max_y) {
if (!node || y1 > cur_max_y || y2 < cur_min_y) {
return DEFAULT_VALUE;
}
if (y1 <= cur_min_y && y2 >= cur_max_y) {
return node->val;
}
int mid_y = cur_min_y + (cur_max_y - cur_min_y) / 2;
int left_res = query_y(node->left, y1, y2, cur_min_y, mid_y);
int right_res = query_y(node->right, y1, y2, mid_y + 1, cur_max_y);
return merge(left_res, right_res);
}
/**
* @brief Performs a range query on the outer x-tree (rows).
*/
int query_x(NodeX* node, int x1, int x2, int y1, int y2, int cur_min_x, int cur_max_x) {
if (!node || x1 > cur_max_x || x2 < cur_min_x) {
return DEFAULT_VALUE;
}
if (x1 <= cur_min_x && x2 >= cur_max_x) {
// This node's x-range is fully contained, so query its y-tree
return query_y(node->y_tree, y1, y2, min_y, max_y);
}
int mid_x = cur_min_x + (cur_max_x - cur_min_x) / 2;
int left_res = query_x(node->left, x1, x2, y1, y2, cur_min_x, mid_x);
int right_res = query_x(node->right, x1, x2, y1, y2, mid_x + 1, cur_max_x);
return merge(left_res, right_res);
}
/**
* @brief Public interface for a 2D range query.
* @param x1 The starting x-coordinate of the query rectangle.
* @param y1 The starting y-coordinate of the query rectangle.
* @param x2 The ending x-coordinate of the query rectangle.
* @param y2 The ending y-coordinate of the query rectangle.
* @return The aggregated value in the specified rectangle.
*/
int query(int x1, int y1, int x2, int y2) {
return query_x(root, x1, x2, y1, y2, min_x, max_x);
}
};
DynamicSegTree2D st;
void init(int R, int C) {
st = DynamicSegTree2D(0, R - 1, 0, C - 1);
}
void update(int P, int Q, long long K) {
st.update(P, Q, K);
}
long long calculate(int P, int Q, int U, int V) {
return st.query(P, Q, U, V);
}
// // --- Example Usage ---
// void solve() {
// // Define the coordinate boundaries. Can be very large.
// int R = 1e9, C = 1e9;
// init(R, C);
// int q;
// cin >> q;
// while(q--) {
// string op;
// cin >> op;
// if (op == "1") {
// int P, Q, K;
// cin >> P >> Q >> K;
// update(P, Q, K);
// } else if (op == "2") {
// int P, Q, U, V;
// cin >> P >> Q >> U >> V;
// cout << calculate(P, Q, U, V) << '\n';
// }
// }
// }
// signed main() {
// ios_base::sync_with_stdio(false);
// cin.tie(nullptr);
// solve();
// return 0;
// }