結果

問題 No.1891 Static Xor Range Composite Query
ユーザー Gimran Abdullin
提出日時 2022-10-11 18:05:08
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 721 ms / 5,000 ms
コード長 2,637 bytes
コンパイル時間 2,139 ms
コンパイル使用メモリ 203,384 KB
最終ジャッジ日時 2025-02-08 01:24:41
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;

constexpr int MOD = 998244353;

struct Info {
    int k = 1, b = 0;

    Info(int k = 1, int b = 0) : k(k), b(b) {};

    friend Info operator+(Info a, Info b) {
        Info res(1LL * a.k * b.k % MOD, (b.b + 1LL * a.b * b.k) % MOD);
        return res;
    }

    void operator+=(Info b) {
        (*this) = (*this) + b;
    }
};


template<class Info, class Merge = plus<Info>>
struct XORSegmentTree {
    int sz;
    vector<vector<Info>> t;
    const Merge merge;

    XORSegmentTree(vector<Info> A): merge(Merge()) {
        sz = 1 << (__lg(A.size()) + bool(A.size() & (A.size() - 1)));
        t = vector<vector<Info>>(sz << 1);
        for (int i = 0; i < A.size(); i++) {
            t[sz + i] = {A[i]};
        }
        for (int i = sz - 1; i >= 0; i--) {
            int cnt = t[i << 1].size();
            t[i].resize(cnt << 1);
            for (int j = 0; j < cnt; j++) {
                t[i][j] = merge(t[i << 1][j], t[i << 1 | 1][j]);
            }
            for (int j = 0; j < cnt; j++) {
                t[i][j + cnt] = merge(t[i << 1 | 1][j], t[i << 1][j]);
            }
        }
    }

    XORSegmentTree() = default;

    Info rangeSum(int l, int r, int i, int x, int lx, int rx) {
        if (rx <= l || r <= lx) {
            return {};
        } else if (l <= lx && rx <= r) {
            return t[x][i];
        } else {
            int p = (rx - lx) >> 1, mid = (lx + rx) >> 1;
            if ((i & p) == 0) {
                Info resL = rangeSum(l, r, i, x << 1, lx, mid);
                Info resR = rangeSum(l, r, i, x << 1 | 1, mid, rx);
                return merge(resL, resR);
            } else {
                Info resL = {};
                if (r >= mid) {
                    resL = rangeSum(max(l, mid) - p, r - p, i ^ p, x << 1, lx, mid);
                }
                Info resR = {};
                if (l < mid) {
                    resR = rangeSum(l + p, min(r, mid) + p, i ^ p, x << 1 | 1, mid, rx);
                }
                return merge(resR, resL);
            }
        }
    }

    Info rangeSum(int L, int R, int x) {
        return rangeSum(L, R, x, 1, 0, sz);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;

    vector<Info> a(n);
    for (int i = 0; i < n; ++i) {
        int k, b;
        cin >> k >> b;
        a[i] = {k, b};
    }

    XORSegmentTree t(a);

    while (q--) {
        int l, r, i, x;
        cin >> l >> r >> i >> x;
        Info res = t.rangeSum(l, r, i);
        cout << (1LL * res.k * x + res.b) % MOD << '\n';
    }
    return 0;
}
0