結果
| 問題 |
No.1526 Sum of Mex 2
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:06:56 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 62 ms / 3,000 ms |
| コード長 | 8,170 bytes |
| コンパイル時間 | 776 ms |
| コンパイル使用メモリ | 80,092 KB |
| 実行使用メモリ | 7,844 KB |
| 最終ジャッジ日時 | 2025-05-14 13:08:39 |
| 合計ジャッジ時間 | 3,222 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 32 |
ソースコード
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
using namespace std;
// Use long long for sums and potentially large values
typedef long long ll;
// Define a large enough value to represent infinity for the initial minimum comparison.
// Needs to be larger than any possible position value (which is N <= 10^5).
// Using 10^9 + 7, a common large prime, is clearly sufficient.
const ll INF = 1e9 + 7;
// Structure for segment tree nodes
struct Node {
ll min_val; // Stores the minimum value in the range [start, end] covered by this node
};
// Global variables
vector<ll> p; // Base array (conceptually) storing last seen positions p_0, ..., p_N. p[0] = r, p[i] = last_pos(i, r) for i > 0. We don't actually need to store p explicitly since the segment tree holds the values.
vector<Node> tree; // Segment tree array
int N; // Length of the input array A
int base_size; // The number of logical indices we need to cover: 0 to N, so N+1 indices.
int tree_nodes_allocated_size; // Number of leaves in the segment tree (smallest power of 2 >= base_size)
int tree_array_size; // Actual size allocated for the segment tree array (usually 2 * tree_nodes_allocated_size)
// Function to build the segment tree
// node: current node index in tree array (1-based indexing is common)
// start, end: range of indices covered by this node in the conceptual base array
void build(int node, int start, int end) {
if (start == end) {
// Leaf node initialization. If index 'start' is within the logical range [0, N],
// initialize with p[start] (which is 0 initially). Otherwise, use 0 for padding leaves.
if (start < base_size) {
// Initially all last positions are 0.
tree[node] = {0};
} else {
// This part handles indices beyond N used for padding to power of 2 size
tree[node] = {0}; // Padding leaves are initialized to 0
}
} else {
int mid = start + (end - start) / 2;
// Recursively build left and right children
build(2 * node, start, mid);
build(2 * node + 1, mid + 1, end);
// Combine results: the minimum value in this node is the minimum of its children
tree[node] = {min(tree[2 * node].min_val, tree[2 * node + 1].min_val)};
}
}
// Function to update a value in the segment tree (point update)
// node: current node index
// start, end: range covered by this node
// idx: index in the conceptual base array p to update (0 <= idx <= N)
// val: new value (the position r)
void update(int node, int start, int end, int idx, ll val) {
// If index is outside the node's range, return. This handles recursive calls correctly.
if (start > idx || end < idx) {
return;
}
// Leaf node corresponds to idx
if (start == end) {
tree[node].min_val = val;
} else {
// Recursive step: decide whether to go left or right
int mid = start + (end - start) / 2;
if (idx <= mid) { // Check if index is within left child range
update(2 * node, start, mid, idx, val);
} else { // Index must be in right child range
update(2 * node + 1, mid + 1, end, idx, val);
}
// After update in child, update current node's minimum based on children
tree[node].min_val = min(tree[2 * node].min_val, tree[2 * node + 1].min_val);
}
}
// The custom query function to compute the sum T_r = sum_{k=1}^{N+1} min(p_0, ..., p_{k-1})
// node: current node index
// start, end: range of indices covered by this node in the conceptual base array
// current_min: the minimum value found in p[0...start-1] passed down from parent/ancestor calls
ll query_sum(int node, int start, int end, ll current_min) {
// Clip the current node's range [start, end] to the relevant logical range [0, N].
// Nodes/parts of nodes covering indices > N are irrelevant to the sum calculation.
if (start >= base_size) {
return 0; // This entire node range is outside [0, N]
}
int actual_end = min(end, base_size - 1); // Consider only indices up to N
// Optimization: If the minimum value in this node's range [start, end] is already >= current_min,
// then for all k such that k-1 is in [start, actual_end], the prefix minimum min(p_0, ..., p_{k-1})
// will be determined by values before index start, which is captured by current_min.
// The contribution to the total sum for this range is (number of relevant elements) * current_min.
// The number of relevant elements is (actual_end - start + 1).
if (tree[node].min_val >= current_min) {
return (ll)(actual_end - start + 1) * current_min;
}
// Base case: Leaf node
if (start == end) {
// Check if this leaf index is within the valid range [0, N]
if (start < base_size) {
// The value at this leaf is p[start]. The prefix minimum up to index start is min(current_min, p[start]).
// This corresponds to the term for k = start + 1 in the sum.
return min(tree[node].min_val, current_min);
} else {
return 0; // Leaf index outside [0, N], contributes 0
}
}
// Recursive step: Query left and right children
int mid = start + (end - start) / 2;
// Query left child. The current_min remains the same.
ll left_sum = query_sum(2 * node, start, mid, current_min);
// For the right child query, the new current_min needs to incorporate the minimum from the left child's range [start, mid].
// This minimum is stored in the left child node `tree[2*node]`.
ll new_current_min = min(current_min, tree[2 * node].min_val);
// Query right child with the updated current_min.
ll right_sum = query_sum(2 * node + 1, mid + 1, end, new_current_min);
// Total sum for this node's range is the sum from left and right children.
return left_sum + right_sum;
}
int main() {
// Faster I/O
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> N;
vector<int> A(N + 1); // Input array A (1-based indexing for problem statement)
for (int i = 1; i <= N; ++i) {
cin >> A[i];
}
// Initialize p array conceptually. We don't need the actual array p.
// p size needed is N+1 to store indices 0 to N.
base_size = N + 1;
// Calculate required size for segment tree leaves (power of 2)
tree_nodes_allocated_size = 1;
while (tree_nodes_allocated_size < base_size) {
tree_nodes_allocated_size *= 2;
}
// Total nodes in segment tree array is typically 2*leaves - 1, use 2*leaves for 1-based index safety.
tree_array_size = 2 * tree_nodes_allocated_size;
tree.resize(tree_array_size);
// Build the segment tree covering range [0, tree_nodes_allocated_size - 1]
// Initial values are all 0 representing initial last positions.
build(1, 0, tree_nodes_allocated_size - 1);
ll total_sum = 0; // Use long long for the final answer
// Iterate through r from 1 to N, processing the array element A[r]
for (int r = 1; r <= N; ++r) {
// Update p[0] to r. This represents the current right endpoint r.
// Updates operate on the segment tree covering the full allocated range [0, tree_nodes_allocated_size - 1]
update(1, 0, tree_nodes_allocated_size - 1, 0, r);
// Update p[A[r]] to r. A[r] is the value at index r. Use it as index into p array.
// Constraint: 1 <= A[i] <= N. So A[r] is a valid index for p[1...N].
update(1, 0, tree_nodes_allocated_size - 1, A[r], r);
// Compute Tr = sum_{k=1}^{N+1} min(p_0, ..., p_{k-1}) using the custom query
// Start query from root node (index 1), covering the full allocated range [0, tree_nodes_allocated_size - 1].
// The query function internally handles restricting calculations to the logical range [0, N].
ll Tr = query_sum(1, 0, tree_nodes_allocated_size - 1, INF);
// Add Tr to the total sum
total_sum += Tr;
}
// Output the final total sum
cout << total_sum << endl;
return 0;
}