結果
| 問題 |
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;
}