結果
| 問題 |
No.833 かっこいい電車
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:09:35 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 153 ms / 2,000 ms |
| コード長 | 11,712 bytes |
| コンパイル時間 | 1,565 ms |
| コンパイル使用メモリ | 102,744 KB |
| 実行使用メモリ | 15,744 KB |
| 最終ジャッジ日時 | 2025-05-14 13:10:57 |
| 合計ジャッジ時間 | 5,420 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 30 |
ソースコード
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <utility> // for pair
#include <algorithm> // for std::max, std::min
#include <cstring> // For memset if needed (global array usually zero-init)
// Using namespace std for convenience.
using namespace std;
// Define long long type alias for large sums.
typedef long long ll;
// Define a constant for maximum N, slightly larger than constraint for safety.
const int MAXN_FT = 100005;
// Fenwick tree array (1-based indexing). Global variables are zero-initialized.
ll ft[MAXN_FT];
// Store the number of cars.
int N;
/**
* @brief Adds a delta value to the element at index idx in the Fenwick tree.
* This operation updates the tree structure to reflect the change.
* Complexity: O(log N)
* @param idx 1-based index of the element to update.
* @param delta The value to add to the element at idx.
*/
void add(int idx, ll delta) {
// Basic bounds check for safety.
if (idx < 1 || idx > N) return;
// Update current node and propagate change upwards to ancestors.
for (; idx <= N; idx += idx & (-idx)) { // idx & (-idx) gives the lowest set bit value.
ft[idx] += delta;
}
}
/**
* @brief Queries the prefix sum up to index idx using the Fenwick tree.
* Calculates the sum of elements from index 1 to idx.
* Complexity: O(log N)
* @param idx 1-based index up to which the sum is required.
* @return The prefix sum A[1] + ... + A[idx].
*/
ll query_prefix(int idx) {
// Handle indices less than 1 - prefix sum is 0.
if (idx < 1) return 0;
// If idx > N, the conceptual sum is up to N. Clamp index.
idx = min(idx, N);
ll sum = 0;
// Traverse downwards from idx following the Fenwick tree structure.
for (; idx > 0; idx -= idx & (-idx)) {
sum += ft[idx];
}
return sum;
}
/**
* @brief Queries the sum of elements in a range [l, r].
* Uses prefix sums: Sum(l, r) = PrefixSum(r) - PrefixSum(l-1).
* Complexity: O(log N)
* @param l 1-based starting index of the range.
* @param r 1-based ending index of the range.
* @return The sum of elements A[l] + ... + A[r].
*/
ll query_range(int l, int r) {
// Handle empty or invalid ranges where l > r.
if (l > r) return 0;
// Calculate range sum using prefix sums.
return query_prefix(r) - query_prefix(l - 1);
}
// Set to store component intervals [l, r], ordered by the left endpoint l.
// Uses std::pair<int, int> to represent intervals.
set<pair<int, int>> components_set;
// Map to store the total attractiveness sum for each component interval [l, r].
// Uses std::pair<int, int> as key and long long as value.
map<pair<int, int>, ll> component_sums;
// Set to store indices x for which the link between car x and car x+1 is active.
set<int> active_links;
/**
* @brief Finds the component interval [l, r] that contains the car x.
* Uses the `components_set` which stores intervals sorted by left endpoint.
* Complexity: O(log K), where K is the number of components (K <= N).
* @param x 1-based index of the car.
* @return A pair {l, r} representing the component interval. Returns {-1, -1} if error/not found.
*/
pair<int, int> find_component(int x) {
// `upper_bound({x, N + 1})` finds the first interval {l', r'} in the set
// such that l' > x. The pair {x, N+1} is used to ensure comparison works correctly:
// compares based on first element `l'`, then second element `r'`.
// Since `r'` cannot be greater than N, this correctly finds the first interval starting after x.
auto it = components_set.upper_bound({x, N + 1});
// If `it` is the beginning of the set, it implies all intervals start after x.
// This state should be unreachable because intervals cover [1, N], and x >= 1.
if (it == components_set.begin()) {
return {-1, -1}; // Indicate error: component not found / inconsistent state.
}
// The interval containing x must start at or before x. This means it must be
// the interval immediately preceding the one pointed to by `it`.
--it; // Move iterator back to the candidate interval {l, r}.
// Now `it` points to an interval {l, r} where l <= x.
// We must verify that x is within this interval's bounds: l <= x <= r.
// it->first is l, it->second is r.
if (x >= it->first && x <= it->second) {
return *it; // Found the correct interval containing x.
} else {
// If x > r, then x falls into a gap between intervals.
// This implies an inconsistent state in `components_set`.
return {-1, -1}; // Indicate error: component not found / inconsistent state.
}
}
int main() {
// Optimize C++ standard streams for faster I/O.
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int Q; // Number of queries
cin >> N >> Q; // Read N (number of cars) and Q (number of queries)
// Read initial attractiveness values into a temporary vector.
vector<ll> initial_A(N + 1);
for (int i = 1; i <= N; ++i) {
cin >> initial_A[i];
}
// Initialize the Fenwick tree using an O(N) approach.
// Assumes ft array is zero-initialized (true for global arrays).
for (int i = 1; i <= N; ++i) {
ft[i] += initial_A[i]; // Initialize node i with its base value A[i]
int parent = i + (i & -i); // Calculate the index of the parent node in the Fenwick tree
if (parent <= N) {
// Add the contribution of node i to its parent.
// This propagates sums upwards to build the tree structure.
ft[parent] += ft[i];
}
}
// Initialize components: Initially, each car `i` forms its own component `[i, i]`.
for (int i = 1; i <= N; ++i) {
// Insert the component interval into the set.
components_set.insert({i, i});
// Store the initial attractiveness sum (just A[i]) for this component.
component_sums[{i, i}] = initial_A[i];
}
// Process Q queries.
for (int q = 0; q < Q; ++q) {
int type; // Query type
cin >> type;
// Handle connect (1) or separate (2) queries.
if (type <= 2) {
int x; // Index for connect/separate operation
cin >> x;
// Problem statement guarantees 1 <= x < N for these types.
if (type == 1) { // connect x <-> x+1
// If the link between x and x+1 is already active, do nothing.
if (active_links.count(x)) continue;
// Mark the link x <-> x+1 as active.
active_links.insert(x);
// Find the components containing car x and car x+1.
pair<int, int> comp1 = find_component(x);
pair<int, int> comp2 = find_component(x + 1);
// Error check: If find_component returned error, skip.
if (comp1.first == -1 || comp2.first == -1) continue;
// If x and x+1 are already in the same component, this indicates a logical error,
// because the link was marked as inactive. Skip for safety.
if (comp1 == comp2) continue;
// Extract component bounds and sums for merging.
int l1 = comp1.first, r1 = comp1.second;
int l2 = comp2.first, r2 = comp2.second;
ll sum1 = component_sums[comp1];
ll sum2 = component_sums[comp2];
// Remove the old components from the set and map.
components_set.erase(comp1);
components_set.erase(comp2);
component_sums.erase(comp1);
component_sums.erase(comp2);
// Create the new merged component interval [l1, r2].
pair<int, int> new_comp = {l1, r2};
// Insert the new component into the set.
components_set.insert(new_comp);
// The sum of the merged component is the sum of the parts.
component_sums[new_comp] = sum1 + sum2;
} else { // type == 2, separate x <-> x+1
// If the link between x and x+1 is not active, do nothing.
if (!active_links.count(x)) continue;
// Mark the link x <-> x+1 as inactive.
active_links.erase(x);
// Find the component containing x (and thus x+1, since link was active).
pair<int, int> comp = find_component(x);
// Error check: If find_component returned error, skip.
if (comp.first == -1) continue;
int l = comp.first, r = comp.second;
// Remove the old component [l, r] from the set and map.
components_set.erase(comp);
component_sums.erase(comp);
// Create two new component intervals: [l, x] and [x+1, r].
pair<int, int> new_comp1 = {l, x};
pair<int, int> new_comp2 = {x + 1, r};
// Insert the new components into the set.
components_set.insert(new_comp1);
components_set.insert(new_comp2);
// Recalculate the sums for the new components using the Fenwick tree,
// which reflects the current attractiveness values including remodels.
ll sum1 = query_range(l, x);
ll sum2 = query_range(x + 1, r);
// Store the calculated sums in the map.
component_sums[new_comp1] = sum1;
component_sums[new_comp2] = sum2;
}
} else { // Handle remodel (3) or attractiveness (4) queries.
int x; // Index for remodel/attractiveness query
cin >> x;
// Problem statement guarantees 1 <= x <= N for these types.
if (type == 3) { // remodel x
ll delta = 1; // Attractiveness increases by 1.
// Update the Fenwick tree to reflect the change in A[x].
add(x, delta);
// Find the component containing car x.
pair<int, int> comp = find_component(x);
// Error check: If find_component returned error, skip.
if (comp.first == -1) continue;
// Increment the stored sum for this component in the map.
// Check if the component exists in the map first for robustness.
if (component_sums.count(comp)) {
component_sums[comp] += delta;
} // If not found, implies inconsistency - possibly ignore update.
} else { // type == 4, attractiveness x
// Find the component containing car x.
pair<int, int> comp = find_component(x);
// Error check: If find_component returned error, print error message or 0.
if (comp.first == -1) {
// This path implies an issue, output 0 or error message.
// Let's output 0 as a failsafe.
cout << 0 << "\n"; continue;
}
// Print the stored sum for this component from the map.
if (component_sums.count(comp)) {
cout << component_sums[comp] << "\n";
} else {
// Inconsistent state: component found in set but not in map.
// Output 0 or recompute sum from FT as a fallback.
// Outputting 0 to indicate issue.
cout << 0 << "\n";
}
}
}
}
return 0; // Indicate successful execution.
}