#1083750 (C++17) No.259 セグメントフィッシング＋

• 問題: No.259 セグメントフィッシング＋
• ユーザー: qwewe
• 提出日時: 2025-05-14 12:59:39
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 41 ms / 2,000 ms
• コード長: 7,553 bytes
• コンパイル時間: 600 ms
• コンパイル使用メモリ: 75,444 KB
• 実行使用メモリ: 7,844 KB
• 最終ジャッジ日時: 2025-05-14 13:00:42
• 合計ジャッジ時間: 3,071 ms
• ジャッジサーバーID （参考情報）: judge3 / judge4

ファイルパターン	結果
sample	AC * 3
other	AC * 23

ソースコード

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

// Define long long type for potentially large fish counts and sums.
typedef long long ll;

// Set a constant for the maximum possible value of P = 2N. N <= 2e5, so P <= 4e5.
// Add a small buffer for safety. The BIT array uses 1-based indexing internally.
const int MAXP = 400005; 
// Declare the Fenwick tree (BIT) array. Use long long to store sums, as total fish count can exceed 32-bit integer limit.
ll bit[MAXP];
// Variable to store the period P = 2N of the fish movement cycle.
int P; 

/**
 * @brief Adds 'delta' to the element at index 'idx' in the Fenwick tree (BIT).
 * The BIT uses 1-based indexing. Updates index 'idx' and all its ancestors.
 * 
 * @param idx The 1-based index to update.
 * @param delta The value to add at index 'idx'.
 */
void add(int idx, ll delta) {
    // Basic bounds check for 1-based index.
    if (idx <= 0 || idx > P) return; 
    // Traverse up the tree, updating relevant nodes.
    for (; idx <= P; idx += idx & -idx) { // `idx & -idx` gives the lowest set bit
        bit[idx] += delta;
    }
}

/**
 * @brief Queries the prefix sum up to index 'idx' (sum of elements from index 1 to idx).
 * The BIT uses 1-based indexing.
 * 
 * @param idx The 1-based index up to which the sum is required.
 * @return The prefix sum up to index 'idx'.
 */
ll query(int idx) {
    // Handle index out of bounds cases. Return 0 for invalid/zero index.
    if (idx <= 0) return 0; 
    // Clamp index to the maximum valid index P if it exceeds bounds.
    if (idx > P) idx = P; 
    ll sum = 0;
    // Traverse down from 'idx' using parent links, summing values.
    for (; idx > 0; idx -= idx & -idx) {
        sum += bit[idx];
    }
    return sum;
}

/**
 * @brief Calculates the sum of elements in a range [A, B] modulo P.
 * The range is defined on 0-based indices [0, P-1]. Handles wrap-around cases where A > B.
 * 
 * @param A The start index of the range (0-based).
 * @param B The end index of the range (0-based).
 * @return The sum of elements in the specified range modulo P.
 */
ll range_sum(int A, int B) {
    // Validate input indices A and B are within [0, P-1]. Defensive check.
     if (A < 0 || A >= P || B < 0 || B >= P) {
         // Invalid range indices, this might indicate a logic error elsewhere.
         return 0; 
    }
    
    // Convert 0-based indices A, B to 1-based indices used by the BIT.
    int A_1based = A + 1;
    int B_1based = B + 1;

    // Case 1: Standard interval [A, B] where A <= B.
    if (A <= B) {
        // The sum over [A, B] (0-based) is sum[1..B+1] - sum[1..A].
        // Using BIT functions: query(B_1based) - query(A_1based - 1).
        return query(B_1based) - query(A_1based - 1);
    } 
    // Case 2: Wrap-around interval [A, P-1] U [0, B] where A > B.
    else {
        // The sum is sum over [A, P-1] + sum over [0, B].
        // Using BIT functions: (query(P) - query(A_1based - 1)) + query(B_1based).
        return (query(P) - query(A_1based - 1)) + query(B_1based);
    }
}

int main() {
    // Optimize standard input/output operations for speed.
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N; // Length of the fishing spot interval [0, N)
    int Q; // Number of queries
    cin >> N >> Q;

    // Calculate the period P = 2N based on the fish movement rules.
    P = 2 * N; 

    // Process Q queries sequentially.
    for (int i = 0; i < Q; ++i) {
        char type; // Type of query: 'L', 'R', or 'C'.
        cin >> type;

        // If query type is 'L' or 'R', it's a fish release event.
        if (type == 'L' || type == 'R') {
            ll t; // Time of release (up to 10^8).
            int y; // Position of release (0 <= y < N). Use int, N <= 2e5.
            ll z; // Number of fish released (up to 10^8). Use ll.
            cin >> t >> y >> z;

            ll k0; // Initial coordinate k0 in the state space [0, P-1].
            if (type == 'L') {
                // Fish released facing left at position y. Initial state (y, Left).
                // Map this state to coordinate k0 = 2N - 1 - y.
                k0 = (ll)2 * N - 1 - y;
            } else { // type == 'R'
                // Fish released facing right at position y. Initial state (y, Right).
                // Map this state to coordinate k0 = y.
                k0 = y;
            }

            // Calculate the invariant K for this batch of fish. 
            // K = (k0 - t) mod P. The position coordinate k(t) = (K + t) mod P.
            // Use modular arithmetic properties to ensure K is non-negative.
            // t % P ensures we handle large t correctly relative to the period P.
            ll K = (k0 - (t % P) + P) % P; 
            
            // Add the 'z' fish to the Fenwick tree at index K+1 (BIT is 1-based).
            add(K + 1, z);

        } 
        // If query type is 'C', it's a count query.
        else { 
            ll t; // Time of query (up to 10^8).
            int y, z_coord; // Query interval [y, z_coord). Use int for coordinates.
            cin >> t >> y >> z_coord;

            ll total_fish = 0; // Initialize the count for this query.

            // --- Contribution from fish potentially moving Right ---
            // These fish have state coordinates k(t) in [0, N-1].
            // Their position x(t) = k(t).
            // Condition to be counted: y <= x(t) < z_coord  =>  y <= k(t) < z_coord.
            // Combined condition on k(t): k(t) must be in the interval [max(0, y), min(N-1, z_coord-1)].
            int A1 = max(0, y); // Start of interval for k(t)
            int B1 = min(N - 1, z_coord - 1); // End of interval for k(t)
            
            // Check if the interval [A1, B1] is valid (non-empty).
            if (A1 <= B1) { 
                // Map the target k(t) interval [A1, B1] to the corresponding K interval [A1', B1'].
                // K = (k(t) - t) mod P.
                int A1_prime = (A1 - (int)(t % P) + P) % P; // Use (int)(t % P) as P is int range.
                int B1_prime = (B1 - (int)(t % P) + P) % P;
                // Add the sum over this K interval [A1', B1'] using range_sum function.
                total_fish += range_sum(A1_prime, B1_prime);
            }

            // --- Contribution from fish potentially moving Left ---
            // These fish have state coordinates k(t) in [N, 2N-1].
            // Their position x(t) = 2N - 1 - k(t).
            // Condition to be counted: y <= x(t) < z_coord  =>  y <= 2N - 1 - k(t) < z_coord.
            // Rearranging for k(t): 2N - z_coord <= k(t) <= 2N - 1 - y.
            // Combined condition on k(t): k(t) must be in [max(N, 2N - z_coord), min(2N - 1, 2N - 1 - y)].
            int A2 = max(N, 2 * N - z_coord); // Start of interval for k(t)
            int B2 = min(2 * N - 1, 2 * N - 1 - y); // End of interval for k(t)

            // Check if the interval [A2, B2] is valid (non-empty).
             if (A2 <= B2) { 
                // Map the target k(t) interval [A2, B2] to the corresponding K interval [A2', B2'].
                int A2_prime = (A2 - (int)(t % P) + P) % P;
                int B2_prime = (B2 - (int)(t % P) + P) % P;
                // Add the sum over this K interval [A2', B2'] using range_sum function.
                total_fish += range_sum(A2_prime, B2_prime);
            }

            // Output the final calculated total fish count for the query interval.
            cout << total_fish << "\n";
        }
    }

    return 0;
}