#1084025 (C++17) No.1394 Changing Problems

• 問題: No.1394 Changing Problems
• ユーザー: qwewe
• 提出日時: 2025-05-14 13:14:59
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: WA
• 実行時間: -
• コード長: 11,344 bytes
• コンパイル時間: 758 ms
• コンパイル使用メモリ: 86,668 KB
• 実行使用メモリ: 32,972 KB
• 最終ジャッジ日時: 2025-05-14 13:16:02
• 合計ジャッジ時間: 7,401 ms
• ジャッジサーバーID （参考情報）: judge5 / judge3

ファイルパターン	結果
sample	AC * 3
other	AC * 24 WA * 5

ソースコード

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <limits> // Required for numeric_limits

using namespace std;

// Define long long type for potentially large numbers
typedef long long ll;

// Use standard limits for min/max identity elements for segment trees
const ll LL_INF = numeric_limits<ll>::max();
// Use a sufficiently small value for negative infinity to avoid overflow issues
// Any value smaller than minimum possible A_i - (N-2) is okay.
const ll LL_NEG_INF = -4e18; 

// Segment Tree node structure for Range Maximum Query
// Used to efficiently find T_max = max(0, max_i(A_i - (N-2)))
struct MaxSegTreeNode {
    ll max_val = LL_NEG_INF; // Initialize with smallest possible value
};

vector<MaxSegTreeNode> max_seg_tree; // Segment tree array for T_max
vector<ll> A_for_Tmax; // Stores A_i - (N-2) values for leaf nodes

// Build the segment tree for T_max
void build_max_tree(int node, int start, int end) {
    if (start == end) {
        // Leaf node corresponds to an element A_i - (N-2)
        if (start < A_for_Tmax.size()) {
             max_seg_tree[node].max_val = A_for_Tmax[start];
        }
    } else {
        int mid = start + (end - start) / 2;
        build_max_tree(2 * node, start, mid);
        build_max_tree(2 * node + 1, mid + 1, end);
        // Internal node stores the maximum of its children
        max_seg_tree[node].max_val = max(max_seg_tree[2 * node].max_val, max_seg_tree[2 * node + 1].max_val);
    }
}

// Update a value in the segment tree for T_max
void update_max_tree(int node, int start, int end, int idx, ll val) {
    // Check if index is within node's range
     if (start > idx || end < idx) return; 
    if (start == end) {
        // Update leaf node value
        max_seg_tree[node].max_val = val;
    } else {
        int mid = start + (end - start) / 2;
        // Recurse down to the correct child
        if (idx <= mid) { 
            update_max_tree(2 * node, start, mid, idx, val);
        } else {
            update_max_tree(2 * node + 1, mid + 1, end, idx, val);
        }
        // Update internal node value based on children
        max_seg_tree[node].max_val = max(max_seg_tree[2 * node].max_val, max_seg_tree[2 * node + 1].max_val);
    }
}

// Query the maximum value in a range [l, r] in the segment tree for T_max
ll query_max_tree(int node, int start, int end, int l, int r) {
    // Check for invalid range or range outside node's responsibility
     if (r < start || end < l || l > r) { 
        return LL_NEG_INF; // Return identity element for max
    }
    // If node's range is fully contained within query range
    if (l <= start && end <= r) {
        return max_seg_tree[node].max_val;
    }
    // Recurse down to children
    int mid = start + (end - start) / 2;
    ll p1 = query_max_tree(2 * node, start, mid, l, r);
    ll p2 = query_max_tree(2 * node + 1, mid + 1, end, l, r);
    // Combine results from children
    return max(p1, p2);
}


// Segment Tree node structure for Range Add and Range Minimum Query
// Used to efficiently find min M(r) = min (K * sum_p + f(r)) where f(r) = (K+1)r - K S_r
struct MinSegTreeNode {
    ll min_val = LL_INF; // Initialize with largest possible value
    ll lazy = 0; // Lazy tag for range updates
};

vector<MinSegTreeNode> min_seg_tree; // Segment tree array for f(r) values
vector<ll> initial_f_values; // Stores initial f(r) values for leaf nodes

// Push lazy updates down to children
void push(int node, int start, int end) { 
     if (min_seg_tree[node].lazy != 0 && start != end) { // Only push if not a leaf and lazy tag exists
        // Apply lazy tag to children's min_val and lazy tag
        min_seg_tree[2 * node].min_val += min_seg_tree[node].lazy;
        min_seg_tree[2 * node].lazy += min_seg_tree[node].lazy;
        min_seg_tree[2 * node + 1].min_val += min_seg_tree[node].lazy;
        min_seg_tree[2 * node + 1].lazy += min_seg_tree[node].lazy;
        // Clear current node's lazy tag
        min_seg_tree[node].lazy = 0;
    }
}

// Build the segment tree for f(r) values
void build_min_tree(int node, int start, int end) {
    if (start == end) {
        // Leaf node corresponds to an initial f(r) value
         if (start < initial_f_values.size()) {
              min_seg_tree[node].min_val = initial_f_values[start];
         } 
    } else {
        int mid = start + (end - start) / 2;
        build_min_tree(2 * node, start, mid);
        build_min_tree(2 * node + 1, mid + 1, end);
        // Internal node stores the minimum of its children
        min_seg_tree[node].min_val = min(min_seg_tree[2 * node].min_val, min_seg_tree[2 * node + 1].min_val);
    }
}

// Update range [l, r] by adding delta
void update_min_tree(int node, int start, int end, int l, int r, ll delta) {
    // Check for invalid range or range outside node's responsibility
    if (r < start || end < l || l > r) { 
        return;
    }
    // If node's range is fully contained within update range
    if (l <= start && end <= r) {
        min_seg_tree[node].min_val += delta;
        min_seg_tree[node].lazy += delta;
    } else {
        // Push lazy updates before recursing
        push(node, start, end); 
        int mid = start + (end - start) / 2;
        // Recurse down to children
        update_min_tree(2 * node, start, mid, l, r, delta);
        update_min_tree(2 * node + 1, mid + 1, end, l, r, delta);
        // Update internal node value based on children
        min_seg_tree[node].min_val = min(min_seg_tree[2 * node].min_val, min_seg_tree[2 * node + 1].min_val);
    }
}

// Query the minimum value in a range [l, r] in the segment tree for f(r)
ll query_min_tree(int node, int start, int end, int l, int r) {
    // Check for invalid range or range outside node's responsibility
    if (r < start || end < l || l > r) { 
        return LL_INF; // Return identity element for min
    }
    // If node's range is fully contained within query range
    if (l <= start && end <= r) {
        return min_seg_tree[node].min_val;
    }
    // Push lazy updates before recursing
    push(node, start, end); 
    int mid = start + (end - start) / 2;
    // Recurse down to children
    ll p1 = query_min_tree(2 * node, start, mid, l, r);
    ll p2 = query_min_tree(2 * node + 1, mid + 1, end, l, r);
    // Combine results from children
    return min(p1, p2);
}


int main() {
    // Faster I/O
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    cin >> N;

    vector<ll> A(N); // Store the initial array A
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
    }

    // Handle the N=1 case separately as the main logic relies on K = N-1 > 0.
    if (N == 1) {
        int Q;
        cin >> Q;
        while (Q--) {
            int i; // Query index (1-based)
            ll x; // New value
            cin >> i >> x;
            A[i - 1] = x; // Update A
            // For N=1, the minimum operations needed is max(0, A[0] - (N-2)) = max(0, A[0] - (-1)) = max(0, A[0] + 1)
            cout << max(0LL, A[0] + 1) << "\n";
        }
        return 0;
    }

    // K = N-1 is used frequently in calculations
    ll K = N - 1;
    // N-2 is the target upper bound for A_i values
    ll N_minus_2 = N - 2;

    // Initialize segment tree for T_max calculation
    A_for_Tmax.resize(N);
     for(int i=0; i<N; ++i) {
        // Store A_i - (N-2) for efficient T_max query later
        A_for_Tmax[i] = A[i] - N_minus_2;
     }
    // Allocate memory for the segment tree (4*N is safe)
    max_seg_tree.resize(4 * N); 
    // Build the tree based on initial values
    build_max_tree(1, 0, N - 1);

    // Initialize structures for M' calculation
    ll current_sum_p = 0; // Stores sum of p_i = floor(A_i / K)
    vector<ll> cnt(K, 0); // Stores counts of remainders b_i = A_i % K
    vector<ll> p_vals(N); // Stores p_i for each A_i
    vector<ll> b_vals(N); // Stores b_i for each A_i

    // Calculate initial p_i, b_i, sum_p, and counts
    for (int i = 0; i < N; ++i) {
        // Since A[i] >= 0, standard C++ division and modulo work as floor division/modulo
        p_vals[i] = A[i] / K;
        b_vals[i] = A[i] % K;
        current_sum_p += p_vals[i];
        cnt[b_vals[i]]++;
    }

    // Calculate initial values of f(r) = (K+1)r - K S_r
    initial_f_values.resize(K);
    // S array stores prefix sums of cnt: S[r] = sum_{j=0}^{r-1} cnt[j]
    vector<ll> S(K + 1, 0); 
    for (int r = 0; r < K; ++r) {
        S[r+1] = S[r] + cnt[r];
    }
    
    for (int r = 0; r < K; ++r) {
        // Calculate f(r) using the prefix sum S[r]
        initial_f_values[r] = (K + 1) * (ll)r - K * S[r];
    }

    // Build segment tree for f(r) values
    min_seg_tree.resize(4 * K); 
    // Only build if K > 0 (i.e., N >= 2)
    if (K > 0) { 
         build_min_tree(1, 0, K - 1);
    }

    // Process Queries
    int Q;
    cin >> Q;
    while (Q--) {
        int i_idx; // Query index (1-based)
        ll x; // New value for A[i_idx-1]
        cin >> i_idx >> x;
        i_idx--; // Adjust to 0-based index

        // Update T_max segment tree with the new value x - (N-2)
        update_max_tree(1, 0, N - 1, i_idx, x - N_minus_2);
        // Query the overall maximum value from the T_max tree
        ll current_max_A_minus_N2 = query_max_tree(1, 0, N - 1, 0, N - 1);
        // T_max is max(0, overall maximum)
        ll T_max = max(0LL, current_max_A_minus_N2);

        // Update M' related structures based on the change in A[i_idx]
        ll old_p = p_vals[i_idx]; // Old p value
        ll old_b = b_vals[i_idx]; // Old remainder value
        
        // Remove effect of old value
        current_sum_p -= old_p;
        cnt[old_b]--;
        
        // Update the f(r) segment tree due to change in cnt[old_b]
        if (K > 0) { 
             // Decrementing cnt[old_b] increases f(r) by K for all r > old_b
             // Apply range update [old_b + 1, K - 1] with delta = K
             if (old_b + 1 <= K - 1) { // Check if range is valid
                update_min_tree(1, 0, K - 1, old_b + 1, K - 1, K);
            }
        }

        // Calculate new p and b values for x
        ll new_p = x / K;
        ll new_b = x % K;
        
        // Store new values
        p_vals[i_idx] = new_p;
        b_vals[i_idx] = new_b;
        
        // Add effect of new value
        current_sum_p += new_p;
        cnt[new_b]++;
        
        // Update the f(r) segment tree due to change in cnt[new_b]
        if (K > 0) {
            // Incrementing cnt[new_b] decreases f(r) by K for all r > new_b
            // Apply range update [new_b + 1, K - 1] with delta = -K
            if (new_b + 1 <= K - 1) { // Check if range is valid
                update_min_tree(1, 0, K - 1, new_b + 1, K - 1, -K);
            }
        }
        
        // Query the minimum f(r) value from the updated segment tree
        ll min_f_r = 0; // Default for K=0 (N=1 case)
        if (K > 0) { // If K>=1 (N>=2)
            min_f_r = query_min_tree(1, 0, K - 1, 0, K - 1);
        } 

        // Calculate M' using the current sum_p and min_f_r
        // M' = min_r M(r) = min_r (K * sum_p + f(r)) = K * sum_p + min_r f(r)
        ll M_prime = K * current_sum_p + min_f_r;

        // The final answer is the maximum of T_max and M'
        cout << max(T_max, M_prime) << "\n";
    }

    return 0;
}