結果
| 問題 |
No.1891 Static Xor Range Composite Query
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:01:28 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 723 ms / 5,000 ms |
| コード長 | 9,057 bytes |
| コンパイル時間 | 915 ms |
| コンパイル使用メモリ | 96,536 KB |
| 実行使用メモリ | 81,228 KB |
| 最終ジャッジ日時 | 2025-05-14 13:03:53 |
| 合計ジャッジ時間 | 13,581 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 30 |
ソースコード
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm> // For std::min, std::max
// Use long long for indices and intermediate calculations
using ll = long long;
ll N; // Length of the sequence of functions. Assumed to be power of 2.
int LOGN; // log2(N)
const ll MOD = 998244353; // Modulus for calculations
// Helper function for modular addition
ll add_mod(ll a, ll b) {
ll res = a + b;
// Adjust result to be within [0, MOD-1]
if (res >= MOD) res -= MOD;
if (res < 0) res += MOD;
return res;
}
// Helper function for modular multiplication
ll mul_mod(ll a, ll b) {
ll res = (a * b) % MOD;
// Adjust result to be within [0, MOD-1]
if (res < 0) res += MOD;
return res;
}
// Structure to represent a linear function f(x) = ax + b
struct LinearFunc {
ll a, b; // Coefficients a and b
// Default constructor for identity function f(x) = 1*x + 0
LinearFunc(ll _a = 1, ll _b = 0) : a(_a), b(_b) {}
// Computes the composition (this o other)(x) = this(other(x))
// Composition order convention: If F = f2 o f1, then F(x) = f2(f1(x)).
// In segment tree context, if node combines Left and Right children,
// Parent = Right.compose(Left) corresponds to applying Left then Right.
LinearFunc compose(const LinearFunc& other) const {
// this(x) = a*x + b
// other(x) = other.a*x + other.b
// this(other(x)) = a * (other.a * x + other.b) + b
// = (a * other.a) * x + (a * other.b + b)
ll new_a = mul_mod(a, other.a);
ll new_b = add_mod(mul_mod(a, other.b), b);
return LinearFunc(new_a, new_b);
}
// Apply the linear function to a value x
ll apply(ll x) const {
ll res = add_mod(mul_mod(a, x), b);
return res;
}
};
// Precomputed table storing composite functions
// Comp[s][idx] stores the composite function related to level 's' and index 'idx'.
// The specific meaning of idx depends on the precomputation logic derived from FWHT-like structure.
std::vector<std::vector<LinearFunc>> Comp;
// Precomputation function to fill the Comp table
// This function computes composite functions for all dyadic intervals and all relevant XOR parameters ('p_low')
// Time complexity: O(N log N)
void precompute() {
// Iterate through levels of the segment tree / decomposition structure, from s=1 up to LOGN
for (int s = 1; s <= LOGN; ++s) {
// level_len is the size of intervals at the previous level (s-1)
ll level_len = 1LL << (s - 1);
// current_len is the size of intervals at the current level (s)
ll current_len = 1LL << s;
// Number of blocks of size current_len in the range [0, N)
ll num_blocks = N / current_len;
// Iterate over each block k at the current level s
for (ll k = 0; k < num_blocks; ++k) {
// Iterate over all possible values of p_low, which has s bits
for (ll p_low = 0; p_low < current_len; ++p_low) {
// Extract the highest bit of p_low (the bit at position s-1)
ll p_high_bit = (p_low >> (s - 1)) & 1;
// Extract the lower s-1 bits of p_low
// The mask `level_len - 1` gives a mask with s-1 ones.
ll p_prime_low = p_low & (level_len - 1);
// Indices of the two child blocks at level s-1
ll kL = k * 2; // Left child block index
ll kR = k * 2 + 1; // Right child block index
// Calculate the indices into Comp[s-1] table for the children results
// These indices depend on child block index (kL/kR) and the lower part of p (p_prime_low)
ll idxL = kL * level_len + p_prime_low;
ll idxR = kR * level_len + p_prime_low;
// Retrieve precomputed functions for children intervals
LinearFunc CompL = Comp[s - 1][idxL];
LinearFunc CompR = Comp[s - 1][idxR];
// Calculate the index into Comp[s] table for the current state (k, p_low)
ll current_idx = k * current_len + p_low;
// Combine the results based on the highest bit of p_low (p_high_bit)
// This corresponds to the butterfly operations in FWHT-like transforms.
if (p_high_bit == 0) {
// If highest bit is 0, XOR doesn't swap halves. The standard order of composition applies:
// The function for the right interval is applied *after* the function for the left interval.
Comp[s][current_idx] = CompR.compose(CompL);
} else {
// If highest bit is 1, XOR effectively swaps the roles of the left and right halves.
// The function for the left interval is applied *after* the function for the right interval.
Comp[s][current_idx] = CompL.compose(CompR);
}
}
}
}
}
// Recursive query function to compute the composite function for range [ql, qr) with XOR parameter p
// Uses standard segment tree query logic, fetching precomputed values for full dyadic interval overlaps.
// Time complexity: O(log N) per query
LinearFunc query_recursive(ll L, ll R, ll ql, ll qr, ll p) {
// Base case 1: Query range [ql, qr) does not overlap with node range [L, R)
if (qr <= L || R <= ql) {
return LinearFunc(); // Return identity function (1, 0)
}
// Base case 2: Query range fully covers node range [L, R)
if (ql <= L && R <= qr) {
ll len = R - L; // Length of the interval [L, R)
if (len == 0) return LinearFunc(); // Empty interval case
// Check if [L, R) is a dyadic interval (length is power of 2) aligned at block boundary (L is multiple of len)
// Bit trick `(len & (len - 1)) == 0` checks if len is power of 2 (and len > 0).
if (len > 0 && (len & (len - 1)) == 0 && (L % len == 0)) {
// Find the level 's' such that 2^s = len
int s = __builtin_ctzll(len); // Count trailing zeros gives log2 for powers of 2
ll k = L / len; // block index k for interval [L, R)
ll p_high = p >> s; // Upper bits of p (relevant for block XORing)
ll p_low = p & ((1LL << s) - 1); // Lower s bits of p (relevant within block)
ll k_prime = k ^ p_high; // Effective block index after XORing with p_high
ll idx = k_prime * len + p_low; // Calculate index in the precomputed table Comp[s]
// Basic boundary check (optional, but good practice)
if (s >= 0 && s <= LOGN && idx >= 0 && idx < N) {
return Comp[s][idx]; // Return the precomputed result
} else {
// Should not happen with correct logic and constraints. Return identity as safe fallback.
return LinearFunc();
}
}
// If not a perfectly aligned dyadic block covered by query, proceed with recursion.
}
// Recursive step: Split interval [L, R) into [L, M) and [M, R)
ll M = L + (R - L) / 2; // Midpoint
// Recursively query left and right children
LinearFunc resL = query_recursive(L, M, ql, qr, p);
LinearFunc resR = query_recursive(M, R, ql, qr, p);
// Combine results: Function for Right interval is applied AFTER function for Left interval.
// This matches the problem statement: f_{r-1} o ... o f_l
return resR.compose(resL);
}
int main() {
// Faster I/O
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int Q; // Number of queries
std::cin >> N >> Q;
// Calculate LOGN = log2(N) since N is guaranteed power of 2
LOGN = 0;
if (N > 0) {
ll tempN = N;
while(tempN > 1) {
tempN >>= 1;
LOGN++;
}
}
// Initialize the Comp table structure
Comp.resize(LOGN + 1);
for (int s = 0; s <= LOGN; ++s) {
Comp[s].resize(N);
}
// Read the initial N linear functions f_i(x) = a_i * x + b_i
// Store them in the base level Comp[0]
// Comp[0][i] represents the function f_i
for (ll i = 0; i < N; ++i) {
ll a, b;
std::cin >> a >> b;
Comp[0][i] = LinearFunc(a, b);
}
// Perform the precomputation O(N log N)
precompute();
// Process Q queries
for (int i = 0; i < Q; ++i) {
ll l, r, p, x; // Query parameters: range [l, r), XOR value p, initial value x
std::cin >> l >> r >> p >> x;
// Compute the composite function for the query range [l, r) with XOR p
// Query range is [l, r), representing indices l, l+1, ..., r-1
LinearFunc final_func = query_recursive(0, N, l, r, p);
// Apply the final composite function to the initial value x
ll result = final_func.apply(x);
// Output the result
std::cout << result << "\n";
}
return 0;
}