結果
| 問題 |
No.2220 Range Insert & Point Mex
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:00:27 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 104 ms / 2,000 ms |
| コード長 | 8,610 bytes |
| コンパイル時間 | 1,044 ms |
| コンパイル使用メモリ | 86,416 KB |
| 実行使用メモリ | 13,328 KB |
| 最終ジャッジ日時 | 2025-05-14 13:02:41 |
| 合計ジャッジ時間 | 6,341 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 36 |
ソースコード
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
// Use long long for coordinates as they can be up to 10^9
typedef long long ll;
// Structure to represent events on the coordinate line
struct Event {
ll coord; // Coordinate of the event
int type; // Type of event: 1 for start interval, 2 for end interval, 3 for query
int val; // Value a_i for updates, query index for queries
// Custom comparison for sorting events
// Sort primarily by coordinate, secondarily by type
// The type order determines the sequence of operations at the same coordinate:
// 1. Start intervals (+1 updates)
// 2. End intervals (-1 updates)
// 3. Queries
// This ensures the state of the segment tree reflects the set contents exactly AT the query coordinate.
bool operator<(const Event& other) const {
if (coord != other.coord) {
return coord < other.coord;
}
// If coordinates are equal, process events in order: start intervals (1), then end intervals (2), then queries (3).
return type < other.type;
}
};
// Structure for segment tree nodes
struct SegTreeNode {
int min_count; // Stores the minimum count of elements within the node's value range
};
// Global segment tree vector and parameters related to its size and range
vector<SegTreeNode> tree;
int N_val_max; // The maximum value index we need to track, which is N_ops (number of operations)
int seg_tree_leaf_range; // The size of the leaf range [0, seg_tree_leaf_range - 1] covered by the physical tree structure. It's the smallest power of 2 >= N_val_max + 1.
// Build the segment tree recursively
// Initializes all counts to 0.
// node: current node index (1-based)
// L, R: current node's value range [L, R]
void build(int node, int L, int R) {
if (L == R) {
// Leaf node represents a single value. Initialize its count to 0.
tree[node] = {0};
} else {
int mid = L + (R - L) / 2;
build(2 * node, L, mid); // Build left child
build(2 * node + 1, mid + 1, R); // Build right child
// Parent node's min_count is the minimum of its children's min_counts
tree[node].min_count = min(tree[2 * node].min_count, tree[2 * node + 1].min_count);
}
}
// Update the count for a target value in the segment tree
// Used for incrementing count (+1) when an interval starts, and decrementing (-1) when it ends.
// node: current node index
// L, R: current node's value range
// target_val: the value whose count needs update
// delta: change in count (+1 or -1)
void update(int node, int L, int R, int target_val, int delta) {
// If target value is outside the current node's range, stop recursion.
// This check prevents errors if target_val somehow falls outside the valid range [L, R].
if (target_val < L || target_val > R) {
return;
}
if (L == R) {
// Leaf node reached, update its count
tree[node].min_count += delta;
} else {
int mid = L + (R - L) / 2;
// Recurse down to the correct child based on target_val
if (target_val <= mid) {
update(2 * node, L, mid, target_val, delta);
} else {
update(2 * node + 1, mid + 1, R, target_val, delta);
}
// Update current node's min_count based on children's updated minimum counts
tree[node].min_count = min(tree[2 * node].min_count, tree[2 * node + 1].min_count);
}
}
// Query the segment tree for the minimum index with count 0 within the logical range [0, N_val_max]
// This index corresponds to the Mex value.
// node: current node index
// L, R: current node's value range covered by this physical node
// Returns the minimum index with count 0. Returns -1 only if no such index exists (which shouldn't happen based on problem logic).
int query_min_zero_idx(int node, int L, int R) {
// If minimum count in this node's entire range is > 0, then no element in this range has count 0.
if (tree[node].min_count > 0) {
return -1; // Indicate no zero count found in this subtree
}
// If leaf node reached and min_count is 0 (guaranteed by the check above)
if (L == R) {
// This leaf node corresponds to value L, and its count is 0. Return L.
return L;
}
int mid = L + (R - L) / 2;
// Check left child first because we want the *minimum* index.
int left_res = query_min_zero_idx(2 * node, L, mid);
if (left_res != -1) {
// Found a zero-count index in the left subtree. This must be the minimum.
return left_res;
}
// If not found in left subtree, check the right subtree.
// Since the parent node's min_count is 0 and left child's min_count is > 0,
// the minimum zero-count index must be in the right subtree.
return query_min_zero_idx(2 * node + 1, mid + 1, R);
}
int main() {
// Faster I/O operations
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N_ops; // Number of range insert operations
cin >> N_ops;
vector<Event> events; // Vector to store all coordinate events
for (int i = 0; i < N_ops; ++i) {
ll l, r; // Interval bounds [l, r]
int a; // Value to insert
cin >> l >> r >> a;
// We only care about values 'a' in the range [0, N_ops].
// The Mex value can be at most N_ops, because a set formed from N operations
// can contain at most N distinct values. The set {0, 1, ..., N_ops} has N_ops+1 elements.
// Therefore, S_x cannot contain all elements from {0, ..., N_ops}, meaning Mex(S_x) <= N_ops.
// Filter out operations with a > N_ops as they don't affect the Mex if it's <= N_ops.
// Also ensure a >= 0 as per problem non-negative integer definition.
if (a >= 0 && a <= N_ops) {
// Create event for interval start at coordinate 'l'
events.push_back({l, 1, a});
// Create event for interval end just after coordinate 'r'. Use coordinate 'r+1'.
events.push_back({r + 1, 2, a});
}
}
int Q; // Number of queries
cin >> Q;
vector<int> results(Q); // Vector to store results for each query
for (int i = 0; i < Q; ++i) {
ll xk; // Query coordinate
cin >> xk;
// Create query event at coordinate 'xk'. Store original query index 'i' in 'val'.
events.push_back({xk, 3, i});
}
// Sort events based on coordinate, then type. This is crucial for the sweep-line approach.
sort(events.begin(), events.end());
// Set up segment tree parameters. The tree covers values from 0 to N_ops.
N_val_max = N_ops;
// Calculate the size required for the segment tree's leaf layer.
// It must be a power of 2 large enough to cover indices up to N_val_max.
seg_tree_leaf_range = 1;
while(seg_tree_leaf_range <= N_val_max) { // Smallest power of 2 >= N_ops+1
seg_tree_leaf_range *= 2;
}
// The segment tree array needs about 2 times the leaf range size.
tree.resize(2 * seg_tree_leaf_range);
// Build the segment tree. It covers the physical range [0, seg_tree_leaf_range - 1].
// The logical range we operate on is [0, N_val_max].
build(1, 0, seg_tree_leaf_range - 1);
// Process events in sorted order (sweep line)
for (const auto& event : events) {
// Updates (type 1 and 2) only affect values within the logical range [0, N_val_max]
if (event.type == 1) { // Start interval event: increment count for value event.val
if (event.val >= 0 && event.val <= N_val_max)
update(1, 0, seg_tree_leaf_range - 1, event.val, 1);
} else if (event.type == 2) { // End interval event: decrement count for value event.val
if (event.val >= 0 && event.val <= N_val_max)
update(1, 0, seg_tree_leaf_range - 1, event.val, -1);
} else { // Query event (type 3)
int query_idx = event.val; // Retrieve original query index
// Query the segment tree for the minimum index (value) with count 0. This is the Mex.
results[query_idx] = query_min_zero_idx(1, 0, seg_tree_leaf_range - 1);
// The query logic guarantees finding the minimum index <= N_val_max if one exists.
// Since Mex <= N_ops is guaranteed, this function should correctly find the Mex.
}
}
// Output the computed Mex values for each query
for (int i = 0; i < Q; ++i) {
cout << results[i] << "\n";
}
return 0;
}