#include #include #include #include #include // for pair #include // for std::max, std::min #include // 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 to represent intervals. set> components_set; // Map to store the total attractiveness sum for each component interval [l, r]. // Uses std::pair as key and long long as value. map, ll> component_sums; // Set to store indices x for which the link between car x and car x+1 is active. set 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 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 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 comp1 = find_component(x); pair 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 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 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 new_comp1 = {l, x}; pair 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 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 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. }