結果

問題 No.1891 Static Xor Range Composite Query
ユーザー qwewe
提出日時 2025-05-14 13:22:35
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,003 ms / 5,000 ms
コード長 5,706 bytes
コンパイル時間 943 ms
コンパイル使用メモリ 92,352 KB
実行使用メモリ 105,960 KB
最終ジャッジ日時 2025-05-14 13:24:48
合計ジャッジ時間 14,781 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <cmath>    // For bit manipulation helpers if needed, though direct bitwise ops are fine
#include <utility>  // For std::pair

using namespace std;

long long MOD = 998244353;

// Represents a function f(x) = ax + b
struct Func {
    long long a, b;

    // Default constructor for identity function f(x) = 1*x + 0
    Func(long long a_val = 1, long long b_val = 0) : a(a_val), b(b_val) {}

    // Apply this function to x
    long long apply(long long x) const {
        long long res = (a * x) % MOD;
        res = (res + b) % MOD;
        if (res < 0) res += MOD; // Ensure positive result
        return res;
    }
};

// Compose two functions: g(f(x))
// g is func2, f is func1
// func2(func1(x)) = a2*(a1*x + b1) + b2 = (a2*a1)*x + (a2*b1 + b2)
Func compose(const Func& func2, const Func& func1) {
    long long new_a = (func2.a * func1.a) % MOD;
    long long new_b = (func2.a * func1.b + func2.b) % MOD;
    if (new_a < 0) new_a += MOD;
    if (new_b < 0) new_b += MOD;
    return Func(new_a, new_b);
}

// S[k][i][mask_val]
// k: level (segment_size is 2^k)
// i: index of the segment in this level (block address)
// mask_val: k-bit mask
vector<vector<vector<Func>>> S;

int N_global; // Store N from input
int H_global; // Max level, log2(N_global)

// Build the data structure
void build_structure(const vector<Func>& base_functions) {
    N_global = base_functions.size();
    if (N_global == 0) return;

    H_global = 0;
    if (N_global > 1) {
        int tempN = N_global;
        while (tempN > 1) {
            tempN >>= 1;
            H_global++;
        }
    }

    S.resize(H_global + 1);

    // Level 0: segments of size 2^0 = 1
    S[0].resize(N_global);
    for (int i = 0; i < N_global; ++i) {
        S[0][i].resize(1); // Mask is 0-bit (always 0)
        S[0][i][0] = base_functions[i];
    }

    // Levels 1 to H_global
    for (int k = 1; k <= H_global; ++k) {
        int segment_size = 1 << k; // 2^k
        int num_segments = N_global / segment_size;
        S[k].resize(num_segments);

        for (int i = 0; i < num_segments; ++i) {
            S[k][i].resize(segment_size); // k-bit mask_val means 2^k possible masks

            for (int mask_val = 0; mask_val < segment_size; ++mask_val) {
                // (k-1)-th bit of mask_val (0-indexed)
                int msb_of_k_bit_mask = (mask_val >> (k - 1)) & 1;
                // Lower (k-1) bits of mask_val
                int lower_mask_bits = mask_val & ((1 << (k - 1)) - 1);

                const Func& left_half_comp = S[k-1][2 * i + msb_of_k_bit_mask][lower_mask_bits];
                const Func& right_half_comp = S[k-1][2 * i + (1 ^ msb_of_k_bit_mask)][lower_mask_bits];
                
                S[k][i][mask_val] = compose(right_half_comp, left_half_comp);
            }
        }
    }
}

// Query for range [query_l, query_r] with XOR value p_val
// current_node_l, current_node_r defines the range of the current segment tree node
Func query_recursive(int current_node_l, int current_node_r, int query_l, int query_r, int p_val) {
    // If current segment is completely outside query range (shouldn't happen with proper initial call and logic)
    if (current_node_l > query_r || current_node_r < query_l) {
        return Func(); // Identity
    }

    int current_segment_len = current_node_r - current_node_l + 1;
    int current_level = 0;
    if (current_segment_len > 1) {
        int tempLen = current_segment_len;
        while(tempLen > 1){
            tempLen >>=1;
            current_level++;
        }
    }
    
    // If current segment is completely within query range
    if (query_l <= current_node_l && current_node_r <= query_r) {
        int block_start_idx_in_N = current_node_l / current_segment_len; 
        int effective_block_idx = block_start_idx_in_N ^ (p_val >> current_level);
        int k_bit_mask_for_S_access = p_val & (current_segment_len - 1); // Mask p_val to current_level LSBs
        return S[current_level][effective_block_idx][k_bit_mask_for_S_access];
    }

    // Partial overlap or current segment contains query range: recurse
    int mid_point = current_node_l + (current_segment_len / 2); 
    Func res_left = Func(); 
    Func res_right = Func(); 
    bool left_taken = false;
    bool right_taken = false;

    if (query_l < mid_point) { // Query overlaps with left child's range
        res_left = query_recursive(current_node_l, mid_point - 1, query_l, query_r, p_val);
        left_taken = true;
    }
    if (query_r >= mid_point) { // Query overlaps with right child's range
        res_right = query_recursive(mid_point, current_node_r, query_l, query_r, p_val);
        right_taken = true;
    }

    if (left_taken && right_taken) return compose(res_right, res_left);
    if (left_taken) return res_left;
    if (right_taken) return res_right;
    
    // Should be unreachable if query_l <= query_r initially
    return Func(); 
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N_input, Q_input;
    cin >> N_input >> Q_input;

    vector<Func> base_functions(N_input);
    for (int i = 0; i < N_input; ++i) {
        cin >> base_functions[i].a >> base_functions[i].b;
    }

    build_structure(base_functions);

    for (int q_idx = 0; q_idx < Q_input; ++q_idx) {
        int l, r, p, x;
        cin >> l >> r >> p >> x;
        // Query range is [l, r-1]. If l == r, it's an empty range, result is x.
        // The problem constraints say 0 <= l_i < r_i <= N, so r-1 >= l, range is non-empty.
        Func composite_func = query_recursive(0, N_global - 1, l, r - 1, p);
        cout << composite_func.apply(x) << "\n";
    }

    return 0;
}
0