結果

問題 No.1891 Static Xor Range Composite Query
ユーザー Gimran AbdullinGimran Abdullin
提出日時 2022-10-11 18:05:08
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 669 ms / 5,000 ms
コード長 2,637 bytes
コンパイル時間 2,227 ms
コンパイル使用メモリ 207,572 KB
実行使用メモリ 68,756 KB
最終ジャッジ日時 2023-09-07 19:18:26
合計ジャッジ時間 11,765 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,376 KB
testcase_01 AC 2 ms
4,380 KB
testcase_02 AC 2 ms
4,380 KB
testcase_03 AC 2 ms
4,376 KB
testcase_04 AC 1 ms
4,376 KB
testcase_05 AC 2 ms
4,380 KB
testcase_06 AC 1 ms
4,376 KB
testcase_07 AC 1 ms
4,380 KB
testcase_08 AC 1 ms
4,376 KB
testcase_09 AC 1 ms
4,380 KB
testcase_10 AC 1 ms
4,376 KB
testcase_11 AC 4 ms
4,376 KB
testcase_12 AC 3 ms
4,380 KB
testcase_13 AC 3 ms
4,376 KB
testcase_14 AC 4 ms
4,376 KB
testcase_15 AC 3 ms
4,380 KB
testcase_16 AC 4 ms
4,376 KB
testcase_17 AC 3 ms
4,380 KB
testcase_18 AC 3 ms
4,376 KB
testcase_19 AC 3 ms
4,376 KB
testcase_20 AC 4 ms
4,376 KB
testcase_21 AC 645 ms
68,652 KB
testcase_22 AC 640 ms
68,664 KB
testcase_23 AC 648 ms
68,756 KB
testcase_24 AC 667 ms
68,644 KB
testcase_25 AC 663 ms
68,632 KB
testcase_26 AC 654 ms
68,704 KB
testcase_27 AC 658 ms
68,628 KB
testcase_28 AC 669 ms
68,756 KB
testcase_29 AC 655 ms
68,660 KB
testcase_30 AC 660 ms
68,632 KB
権限があれば一括ダウンロードができます

ソースコード

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