結果
| 問題 |
No.1441 MErGe
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:01:22 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 392 ms / 1,000 ms |
| コード長 | 11,053 bytes |
| コンパイル時間 | 1,247 ms |
| コンパイル使用メモリ | 96,888 KB |
| 実行使用メモリ | 16,252 KB |
| 最終ジャッジ日時 | 2025-05-14 13:03:33 |
| 合計ジャッジ時間 | 11,409 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 28 |
ソースコード
#include <iostream>
#include <vector>
#include <cstdlib> // Standard library utilities, included for completeness though not directly used for rand/srand now
#include <random> // For mt19937 PRNG
// Use Mersenne Twister PRNG. A fixed seed ensures deterministic behavior, which is useful for debugging and competitive programming contests.
std::mt19937 rng(1337);
// Node structure for the Treap. Using array indices instead of pointers for potentially better cache performance and simpler memory management.
struct Node {
long long value; // The value of the element stored in this node
long long sum; // The sum of values in the subtree rooted at this node (including this node)
int size; // The number of nodes in the subtree rooted at this node (including this node)
unsigned int priority; // Random priority used for Treap balancing (higher priority means closer to the root)
int left, right; // Indices into the 'nodes' array representing the left and right children. 0 represents a null child.
// Default constructor initializes members to zero/null equivalents. Useful for array allocation.
Node() : value(0), sum(0), size(0), priority(0), left(0), right(0) {}
};
// Preallocate storage for all potential nodes. The maximum number of nodes needed is the initial N plus at most Q nodes created by Type 1 queries.
// Add a small buffer (e.g., +5) for safety margin.
const int MAX_NODES = 200000 + 200000 + 5;
Node nodes[MAX_NODES]; // Global array to store all nodes
int nextNodeIdx = 1; // Index for the next available slot in the 'nodes' array. Starts at 1 because index 0 is used to represent null.
// Helper function to get the size of a subtree. Handles the case where nodeIdx is 0 (null).
// Marked inline as a hint to the compiler for potential optimization.
inline int getSize(int nodeIdx) {
// If nodeIdx is 0 (representing null), the size is 0. Otherwise, return the stored size of the node.
return nodeIdx ? nodes[nodeIdx].size : 0;
}
// Helper function to get the sum of values in a subtree. Handles the case where nodeIdx is 0 (null).
// Marked inline for potential optimization.
inline long long getSum(int nodeIdx) {
// If nodeIdx is 0 (representing null), the sum is 0. Otherwise, return the stored sum of the node.
return nodeIdx ? nodes[nodeIdx].sum : 0;
}
// Updates the 'size' and 'sum' fields of a node based on its current children.
// This must be called after any operation that might change the children of a node or their subtrees.
void updateNode(int nodeIdx) {
if (nodeIdx) { // Check if the node index is valid (non-zero)
// The size of the subtree is 1 (for the node itself) plus the sizes of its left and right subtrees.
nodes[nodeIdx].size = 1 + getSize(nodes[nodeIdx].left) + getSize(nodes[nodeIdx].right);
// The sum of the subtree is the value of the node itself plus the sums of its left and right subtrees.
nodes[nodeIdx].sum = nodes[nodeIdx].value + getSum(nodes[nodeIdx].left) + getSum(nodes[nodeIdx].right);
}
}
// Creates a new node with the given value, assigns it a random priority, initializes its fields,
// and returns the index of the newly created node in the 'nodes' array.
int newNode(long long val) {
int currIdx = nextNodeIdx++; // Get the next available index and increment the counter for future allocations.
nodes[currIdx].value = val; // Set the node's value.
nodes[currIdx].sum = val; // Initially, the sum of the subtree is just the node's own value.
nodes[currIdx].size = 1; // Initially, the size of the subtree is 1 (just the node itself).
nodes[currIdx].priority = rng(); // Assign a random priority generated by the mt19937 engine.
nodes[currIdx].left = nodes[currIdx].right = 0; // Initialize children pointers to null (index 0).
return currIdx; // Return the index where the new node is stored.
}
// Splits the Treap rooted at 'rootIdx' into two separate Treaps, L and R.
// The split is performed based on element count: L will contain the first 'k' elements of the sequence represented by the Treap,
// and R will contain the remaining elements.
// The roots of the resulting Treaps L and R are returned via the reference parameters L_idx and R_idx.
void split(int rootIdx, int& L_idx, int& R_idx, int k) {
if (!rootIdx) { // Base case: If the Treap to split is empty, both resulting Treaps are empty.
L_idx = R_idx = 0;
return;
}
int leftSubtreeSize = getSize(nodes[rootIdx].left); // Calculate the size of the left subtree.
// Determine where the split occurs relative to the current root node.
if (leftSubtreeSize < k) {
// The split point is after the left subtree (possibly at the root or in the right subtree).
// This means the current root node belongs to the Left Treap (L).
// We need to recursively split the right subtree. The number of elements needed from the right subtree for L is k - leftSubtreeSize - 1.
split(nodes[rootIdx].right, nodes[rootIdx].right, R_idx, k - leftSubtreeSize - 1);
L_idx = rootIdx; // The current root becomes the root of L. Its right child might have changed in the recursive call.
} else {
// The split point is within the left subtree.
// This means the current root node belongs to the Right Treap (R).
// We need to recursively split the left subtree with the original key k.
split(nodes[rootIdx].left, L_idx, nodes[rootIdx].left, k);
R_idx = rootIdx; // The current root becomes the root of R. Its left child might have changed in the recursive call.
}
// After the split operation potentially modifies the children, update the current node's size and sum.
updateNode(rootIdx);
}
// Merges two Treaps L and R into a single Treap.
// This operation assumes that all elements in the sequence represented by L come before all elements in R.
// Returns the index of the root of the merged Treap.
int merge(int L_idx, int R_idx) {
if (!L_idx) return R_idx; // If L is empty, the result of the merge is simply R.
if (!R_idx) return L_idx; // If R is empty, the result of the merge is simply L.
// The merge logic ensures the Treap property (based on priorities) is maintained.
// We compare priorities of the roots of L and R. The node with higher priority becomes the root of the merged Treap.
if (nodes[L_idx].priority > nodes[R_idx].priority) {
// L's root has higher priority. It becomes the root.
// Its left child remains unchanged. Its right child becomes the result of merging its original right child with R.
nodes[L_idx].right = merge(nodes[L_idx].right, R_idx);
updateNode(L_idx); // Update L's node info since its right child might have changed.
return L_idx; // L's index is the root of the merged Treap.
} else {
// R's root has higher or equal priority. It becomes the root.
// Its right child remains unchanged. Its left child becomes the result of merging L with its original left child.
nodes[R_idx].left = merge(L_idx, nodes[R_idx].left);
updateNode(R_idx); // Update R's node info since its left child might have changed.
return R_idx; // R's index is the root of the merged Treap.
}
}
int main() {
// Optimize C++ standard I/O streams for faster input/output.
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int N; // Number of initial elements in the sequence
int Q; // Number of queries to process
std::cin >> N >> Q;
int root = 0; // Index of the root node of the Treap. Initially 0, representing an empty sequence.
// Read the initial N elements and build the Treap.
for (int i = 0; i < N; ++i) {
long long val;
std::cin >> val;
// Each new element is appended to the end of the sequence.
// This is achieved by merging the current Treap with a new node containing the value.
root = merge(root, newNode(val));
}
// Process the Q queries.
for (int q = 0; q < Q; ++q) {
int type; // Type of the query (1 for merge, 2 for sum)
int l, r; // Range [l, r] for the query (1-based indexing)
std::cin >> type >> l >> r;
// We need to split the Treap into three parts based on the range [l, r]:
// T1: Represents elements with indices 1 to l-1.
// T2: Represents elements with indices l to r.
// T3: Represents elements with indices r+1 to the end of the current sequence.
int T1, T2, T3; // Indices for the roots of these three parts.
int Trem; // Temporary index to hold the root of the Treap after the first split.
// First split: Separate the first l-1 elements (indices 1 to l-1) into T1.
// The rest of the elements (indices l onwards) are stored in Trem.
// The split key is l-1 because split(..., k) extracts the first k elements.
split(root, T1, Trem, l - 1);
// Second split: From Trem (which contains elements from index l onwards),
// separate the elements corresponding to the range [l, r]. This range has r - l + 1 elements.
// These elements form T2. The remaining elements (indices r+1 onwards) form T3.
split(Trem, T2, T3, r - l + 1);
if (type == 1) { // Process Type 1 query: Merge range [l, r].
// Calculate the sum of elements in the range [l, r]. This is simply the sum stored at the root of T2.
long long rangeSum = getSum(T2);
// Create a new node that will represent the merged segment, holding this sum.
int sumNode = newNode(rangeSum);
// Reconstruct the main Treap by merging the parts back together, replacing T2 with sumNode.
// First, merge T1 (elements before l) with the new sumNode.
root = merge(T1, sumNode);
// Then, merge the result with T3 (elements after r).
root = merge(root, T3);
// The nodes originally in T2 are effectively discarded because they are not merged back into the main Treap.
// Their memory slots in the `nodes` array remain, but they are unreachable and considered unused.
} else { // Process Type 2 query: Query sum of range [l, r].
// Calculate the sum of elements in the range [l, r], which is the sum stored at the root of T2.
long long rangeSum = getSum(T2);
// Output the result.
std::cout << rangeSum << "\n";
// Since a Type 2 query should not change the sequence, we must restore the original Treap structure.
// Merge the three parts T1, T2, T3 back together in their original order.
// First, merge T2 and T3 back together.
Trem = merge(T2, T3);
// Then, merge T1 with the result of the previous merge.
root = merge(T1, Trem);
}
}
return 0; // Indicate successful program termination.
}