結果
| 問題 |
No.151 セグメントフィッシング
|
| コンテスト | |
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:06:41 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 19 ms / 5,000 ms |
| コード長 | 10,095 bytes |
| コンパイル時間 | 636 ms |
| コンパイル使用メモリ | 78,900 KB |
| 実行使用メモリ | 7,844 KB |
| 最終ジャッジ日時 | 2025-05-14 13:07:57 |
| 合計ジャッジ時間 | 1,792 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 5 |
| other | AC * 19 |
ソースコード
#include <iostream>
#include <vector>
#include <string>
#include <algorithm> // For min/max
using namespace std;
// Define long long type for large numbers, as fish counts can be up to 10^8
// and total counts can exceed 32-bit integer limits.
typedef long long ll;
// Using a vector for the Fenwick tree (BIT).
// It will store cumulative counts. Size will be N_COORD + 1 for 1-based indexing internally.
vector<ll> bit;
// N_COORD stores 2*N_val, which is the size of our coordinate space (0 to N_COORD-1).
// This coordinate space represents all possible states (position and direction) of a fish.
int N_COORD;
// Add 'val' to the element at index 'idx' (0-based) in the conceptual array.
// This function updates the Fenwick tree structure to reflect the change.
void add(int idx, ll val) {
// Convert to 1-based index because Fenwick trees are typically implemented with 1-based indexing.
idx++;
// Traverse up the tree structure by following the parent links (conceptually).
// Update all nodes that cover the range including 'idx'.
while (idx <= N_COORD) {
bit[idx] += val;
// `idx & (-idx)` gives the lowest set bit. Adding it moves to the next node.
idx += idx & (-idx);
}
}
// Query the prefix sum up to index 'idx' (0-based, inclusive).
// Returns the sum of elements from index 0 to idx in the conceptual array.
ll query(int idx) {
// Handle edge case where index is negative (e.g., querying up to a-1 when a=0).
if (idx < 0) return 0;
// Ensure index does not exceed bounds. If it does, clamp to the maximum valid index.
// query(N_COORD - 1) should return sum of all elements.
idx = min(idx, N_COORD - 1);
// Convert to 1-based index for BIT operations.
idx++;
ll sum = 0;
// Traverse down the tree structure (conceptually) by following links based on lowest set bit.
// Accumulate sums from relevant nodes.
while (idx > 0) {
sum += bit[idx];
// `idx & (-idx)` gives the lowest set bit. Subtracting it moves to the node representing the prefix ending just before this block.
idx -= idx & (-idx);
}
return sum;
}
// Query the sum of elements in the range [a, b) (0-based indices).
// Calculates sum of elements from index a up to (but not including) b.
ll range_query(int a, int b) {
// If the range is invalid or empty (a >= b), return 0.
if (a >= b) {
return 0;
}
// The sum over range [a, b) is equivalent to (sum up to b-1) - (sum up to a-1).
// query(idx) returns sum up to idx inclusive.
ll sum_b_minus_1 = query(b - 1);
ll sum_a_minus_1 = query(a - 1); // query handles idx=-1 correctly, returns 0.
// The range sum is the difference.
return sum_b_minus_1 - sum_a_minus_1;
}
// Custom modulo function to ensure the result is always non-negative.
// Standard C++ % operator can return negative results for negative inputs, which is problematic here.
ll mod(ll x, ll M) {
// `(x % M + M) % M` ensures result is in [0, M-1].
return (x % M + M) % M;
}
int main() {
// Use fast I/O operations to speed up input reading.
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N_val; // Input N: length of the fishing pond interval [0, N). Needs to be int because N <= 2*10^4.
int Q; // Input Q: number of queries. Needs to be int because Q <= 2*10^4.
cin >> N_val >> Q;
// The coordinate space size is 2 * N_val.
N_COORD = 2 * N_val;
// Initialize the Fenwick tree vector. Size N_COORD + 1 for 1-based indexing. All elements initialized to 0.
bit.resize(N_COORD + 1, 0);
// Process each query. Queries are indexed by time t from 1 to Q.
for (int t = 1; t <= Q; ++t) {
char type; // Type of query ('L', 'R', or 'C').
cin >> type;
if (type == 'L' || type == 'R') { // Fish release query (Add fish)
ll y, z; // Position 'y', number of fish 'z'. Both can be large potentially, use ll.
cin >> y >> z;
// Basic validation on position y based on problem constraints 0 <= y < N
// Though problem statement guarantees valid inputs, it's safe programming practice.
// if (y < 0 || y >= N_val) continue; // Skip invalid inputs if any
ll k_initial; // Variable to store the initial coordinate in our 0 to 2N-1 space.
if (type == 'L') {
// Fish starts at position y, moving Left.
// Coordinate mapping: N_val + (N_val - 1 - y).
// This maps states (pos, L) to the range [N, 2N-1].
k_initial = (ll)N_val + (N_val - 1 - y);
} else { // type == 'R'
// Fish starts at position y, moving Right.
// Coordinate mapping: y.
// This maps states (pos, R) to the range [0, N-1].
k_initial = y;
}
// Calculate the effective coordinate offset `k_offset`.
// This value represents the group's state normalized to time t=0.
// `k_offset = (k_initial - t) mod N_COORD`
// Fish released at time `t` with initial coordinate `k_initial` will have coordinate
// `(k_initial + (current_time - t)) mod N_COORD` at `current_time`.
// This is equivalent to `( (k_initial - t) + current_time ) mod N_COORD`.
// So `k_offset = (k_initial - t) mod N_COORD` acts as a phase offset.
ll k_offset = mod(k_initial - t, N_COORD);
// Add the 'z' fish to the count associated with this `k_offset` in the Fenwick tree.
add(k_offset, z);
} else { // type == 'C', Count query
ll y, z_query; // Query asks for fish count in the interval [y, z_query).
cin >> y >> z_query;
// Basic validation on query range [y, z_query).
// Constraints: 0 <= y < z_query <= N_val
// if (y < 0 || z_query > N_val || y >= z_query) { ... handle error or assume valid ... }
ll total_fish = 0; // Accumulator for the total fish count in the queried range.
// Fish positions are determined by their current coordinate `k_current`.
// `k_current = (k_offset + t) mod N_COORD`.
// A 'C' query asks for sum of fish counts `z` where the position `p` derived from `k_current` is in `[y, z_query)`.
// We need to find the set of `k_current` values that map to positions in `[y, z_query)`,
// then shift these ranges by `-t` to find the corresponding `k_offset` values to query in the BIT.
// Part 1: Count fish currently moving Right within the interval [y, z_query).
// Fish moving Right have coordinates `k_current` in [0, N_val - 1].
// Their position `p` is equal to `k_current`.
// We need `k_current` such that `y <= k_current < z_query`.
// Combined conditions: `y <= k_current < min(z_query, N_val)`.
// Target `k_current` interval: `[y, min(z_query, N_val))`.
ll a1 = y;
ll b1 = min((ll)z_query, (ll)N_val);
if (a1 < b1) { // Check if the interval is valid (non-empty).
// Calculate the shifted interval endpoints for `k_offset`. Shift by `-t`.
ll a1_shifted = mod(a1 - t, N_COORD);
ll b1_shifted = mod(b1 - t, N_COORD);
// Query the Fenwick tree over the shifted interval [a1_shifted, b1_shifted).
if (a1_shifted < b1_shifted) {
// If the interval does not wrap around modulo N_COORD.
total_fish += range_query(a1_shifted, b1_shifted);
} else {
// If the interval wraps around (e.g., [5, 2) in mod 10 means indices 5..9 and 0..1).
// Query the two parts separately: [a1_shifted, N_COORD) and [0, b1_shifted).
total_fish += range_query(a1_shifted, N_COORD); // Sum from a1_shifted to N_COORD-1
total_fish += range_query(0, b1_shifted); // Sum from 0 to b1_shifted-1
}
}
// Part 2: Count fish currently moving Left within the interval [y, z_query).
// Fish moving Left have coordinates `k_current` in [N_val, N_COORD - 1].
// Their position `p` is calculated as `p = N_COORD - 1 - k_current`.
// We need `k_current` such that `y <= p < z_query`.
// Substituting p: `y <= N_COORD - 1 - k_current < z_query`.
// Rearranging for `k_current` gives: `N_COORD - z_query <= k_current <= N_COORD - 1 - y`.
// Also `k_current` must be at least `N_val`.
// The combined coordinate range for `k_current`: `[max(N_val, N_COORD - z_query), N_COORD - y)`.
ll a2 = max((ll)N_val, (ll)N_COORD - z_query);
ll b2 = (ll)N_COORD - y;
if (a2 < b2) { // Check if the interval is valid (non-empty).
// Calculate the shifted interval endpoints for `k_offset`. Shift by `-t`.
ll a2_shifted = mod(a2 - t, N_COORD);
ll b2_shifted = mod(b2 - t, N_COORD);
// Query the Fenwick tree over the shifted interval [a2_shifted, b2_shifted).
if (a2_shifted < b2_shifted) {
// If the interval does not wrap around modulo N_COORD.
total_fish += range_query(a2_shifted, b2_shifted);
} else {
// If the interval wraps around.
// Query the two parts separately: [a2_shifted, N_COORD) and [0, b2_shifted).
total_fish += range_query(a2_shifted, N_COORD); // Sum from a2_shifted to N_COORD-1
total_fish += range_query(0, b2_shifted); // Sum from 0 to b2_shifted-1
}
}
// Print the final count for this 'C' query.
cout << total_fish << "\n";
}
}
return 0;
}