結果

問題 No.1891 Static Xor Range Composite Query
ユーザー vjudge1
提出日時 2025-08-31 21:06:13
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 4,558 bytes
コンパイル時間 3,238 ms
コンパイル使用メモリ 286,108 KB
実行使用メモリ 87,688 KB
最終ジャッジ日時 2025-08-31 21:06:28
合計ジャッジ時間 13,755 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 20 TLE * 1 -- * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;

void PRE() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    freopen("error.txt", "w", stderr);
#endif
}
const int mod = 998244353;
/*
 * This segment tree is like normal segment tree but in query you query on position x ^ i for all l <= i <= r
 * you only need to handle apply and merge
 * you must pass n to be power of 2 and when build pad the vector with zeros until it's length be power of 2
*/

const ll inf = 1e18;
struct Node {
    ll a , b;
    Node(ll x = 1 , ll y = 0) {
        a = x , b = y;
    }
    Node operator+(const Node &other) {
        // x * a + b , other.a * x + other.b
        // other.a * (x * a + b) + other.b
        return Node(other.a * a % mod , (other.a * b + other.b) % mod);
    }

};
template<typename T>
struct Seg {
    ll apply(ll old , ll nw) {
        // apply update to certain leaf node
        return old ^ nw;
    }

    T merge(T l , T r) {
        // merge answer
        return l + r;
    }

    int n;
    int N;
    int LOG;
    vector<vector<T>> t;

    Seg(int n = 0) {
        if (n > 0) init(n);
    }

    void init(int _n) {
        n = _n;
        LOG = 0;
        while ((1 << LOG) < n) ++LOG;
        N = 1 << LOG;
        t.assign(4 * N + 5, {});
    }

    vector<T> mergeNode(const vector<T>& L, const vector<T>& R) {
        // merge 2
        int half = (int)L.size();
        vector<T> res(half * 2);
        for (int i = 0; i < half; ++i) res[i] = merge(L[i] , R[i]);
        for (int i = 0; i < half; ++i) res[i + half] = merge(R[i] , L[i]);
        return res;
    }

    void build(int node, int b, int e, const vector<T>& a) {
        if (b == e) {
            t[node].assign(1, (b < (int)a.size() ? a[b] : 0LL));
            return;
        }
        int mid = (b + e) >> 1;
        int L = node << 1, R = L | 1;
        build(L, b, mid, a);
        build(R, mid + 1, e, a);
        t[node] = mergeNode(t[L], t[R]);
    }

    // point update: A[idx] ^= val
    void update_xor(int node, int b, int e, int idx, ll val) {
        if (idx < b || idx > e) return;
        if (b == e) {
            t[node][0] = apply(t[node][0] , val);
            return;
        }
        int mid = (b + e) >> 1;
        int L = node << 1, R = L | 1;
        update_xor(L, b, mid, idx, val);
        update_xor(R, mid + 1, e, idx, val);
        t[node] = mergeNode(t[L], t[R]);
    }

    // query: XOR of A[p ^ x] for p in [i..j]
    T query(int node, int b, int e, int i, int j, int x, int layer = -2) {
        if (i > j || b > j || e < i) return 0LL;
        if (layer == -2) layer = LOG - 1;

        if (i <= b && e <= j) {
            if (layer == -1) return t[node][0];
            int mask = (1 << (layer + 1)) - 1;
            int idx = x & mask;
            if (idx >= (int)t[node].size()) idx %= (int)t[node].size();
            return t[node][idx];
        }

        int mid = (b + e) >> 1;
        int L = node << 1, R = L | 1;

        // check bit 'layer' of x: if 0 -> normal mapping, else swapped mapping
        if (((~x) >> layer) & 1) {
            return merge(query(L, b, mid, i, j, x, layer - 1)  , query(R, mid + 1, e, i, j, x, layer - 1));
        } else {
            // swapped: left part queries map into right subtree and vice versa
            T res = 0;
            int i1 = i, j1 = min(mid, j);
            int i2 = max(i, mid + 1), j2 = j;

            if (i1 <= j1) {
                int ni = mid + 1 + (i1 - b);
                int nj = mid + 1 + (j1 - b);
                res = merge(res , query(R, mid + 1, e, ni, nj, x, layer - 1));
            }
            if (i2 <= j2) {
                int ni = b + (i2 - (mid + 1));
                int nj = b + (j2 - (mid + 1));
                res = merge(res  ,query(L, b, mid, ni, nj, x, layer - 1));
            }
            return res;
        }
    }
};


int main() {
    PRE();
    int n , q;cin >> n >> q;
    int N = 1;
    while (N < n) N <<= 1;
    vector<Node> v(N);
    for (int i = 0;i < n;i++) cin >> v[i].a >> v[i].b;
    Seg<Node> seg(N);
    seg.build(0 , 0 , N - 1 , v);
    for (int i = 0;i < q;i++) {
        int l , r , p , x;
        cin >> l >> r >> p >> x;
        r--;
        // auto res = seg.query(0 , 0 , N - 1 , l , r , p);
        Node res;
        for (int j = l;j <= r;j++) res = res + v[j ^ p];
        // coout <<
        cout << (res.a * x + res.b) % mod << '\n';
    }
}
0