test/yosupo-point-set-range-composite-large-array.test.cpp

• View this file on GitHub
• Last update: 2025-05-13 23:36:19+09:00
• Problem: https://judge.yosupo.jp/problem/point_set_range_composite_large_array

Depends on

• modint/modint.cpp
• segtree/dynamic-segment-tree.cpp

Code

#define PROBLEM \
    "https://judge.yosupo.jp/problem/point_set_range_composite_large_array"

#include <bits/stdc++.h>
using namespace std;

#include "../modint/modint.cpp"
#include "../segtree/dynamic-segment-tree.cpp"

using mint = Modint<998244353>;
using ll = long long;

struct S {
    mint a, b;
    mint f(mint x) { return a * x + b; }
};
S op(S l, S r) { return S{l.a * r.a, l.b * r.a + r.b}; }
S e() { return S{1, 0}; }

int main() {
    ll n, q;
    cin >> n >> q;

    DynamicSegTree<S, op, e, 30> seg;
    while(q--) {
        int t;
        cin >> t;
        if(t == 0) {
            ll p, c, d;
            cin >> p >> c >> d;
            seg.set(p, S{c, d});
        } else {
            ll l, r, x;
            cin >> l >> r >> x;
            cout << seg.prod(l, r).f(x).x << endl;
        }
    }
}

#line 1 "test/yosupo-point-set-range-composite-large-array.test.cpp"
#define PROBLEM \
    "https://judge.yosupo.jp/problem/point_set_range_composite_large_array"

#include <bits/stdc++.h>
using namespace std;

#line 2 "modint/modint.cpp"

template <long long MOD>
struct Modint {
    long long x;
    Modint(long long x_ = 0) : x(x_ % MOD) {
        if(x < 0) x += MOD;
    }
    friend Modint operator+(Modint a, Modint b) { return a.x + b.x; }
    friend Modint operator-(Modint a, Modint b) { return a.x - b.x; }
    friend Modint operator*(Modint a, Modint b) { return a.x * b.x; }
    friend Modint operator/(Modint a, Modint b) { return a * b.inv(); }
    // 4 行コピペ  Alt + Shift + クリックで複数カーソル
    friend Modint& operator+=(Modint& a, Modint b) { return a = a.x + b.x; }
    friend Modint& operator-=(Modint& a, Modint b) { return a = a.x - b.x; }
    friend Modint& operator*=(Modint& a, Modint b) { return a = a.x * b.x; }
    friend Modint& operator/=(Modint& a, Modint b) { return a = a * b.inv(); }
    Modint inv() const { return pow(MOD - 2); }
    Modint pow(long long b) const {
        Modint a = *this, c = 1;
        while(b) {
            if(b & 1) c *= a;
            a *= a;
            b >>= 1;
        }
        return c;
    }
};
#line 2 "segtree/dynamic-segment-tree.cpp"

template <typename S, S (*op)(S, S), S (*e)(), long long WORD>
struct DynamicSegTree {
    void set(long long p, S x) { set(p, WORD - 1, x); }
    S get(long long p) { return get(p, WORD - 1); }
    S all_prod() { return data; }
    S prod(long long l, long long r) { return prod(l, r, 0, 1LL << WORD); }

    DynamicSegTree() : data(e()) { cld[0] = cld[1] = nullptr; }

private:
    DynamicSegTree *cld[2];
    S data;

    DynamicSegTree *child(long long bit) {
        if(cld[bit] == nullptr) {
            cld[bit] = new DynamicSegTree();
        }
        return cld[bit];
    }
    S child_data(long long bit) {
        if(cld[bit] == nullptr)
            return e();
        else
            return cld[bit]->data;
    }

    void update() { data = op(child_data(0), child_data(1)); }

    void set(long long p, long long digit, S x) {
        if(digit == -1) {
            data = x;
        } else {
            long long bit = p >> digit & 1;
            child(bit)->set(p, digit - 1, x);
            update();
        }
    }

    S get(long long p, long long digit) {
        if(digit == -1) {
            return data;
        } else {
            long long bit = p >> digit & 1;
            if(cld[bit] == nullptr)
                return e();
            else
                return cld[bit]->get(p, digit - 1);
        }
    }

    S prod(long long L, long long R, long long l, long long r) {
        if(r <= L || R <= l) {
            return e();
        } else if(L <= l && r <= R) {
            return data;
        } else {
            S res = e();
            if(cld[0] != nullptr) res = cld[0]->prod(L, R, l, (l + r) / 2);
            if(cld[1] != nullptr)
                res = op(res, cld[1]->prod(L, R, (l + r) / 2, r));
            return res;
        }
    }
};
#line 9 "test/yosupo-point-set-range-composite-large-array.test.cpp"

using mint = Modint<998244353>;
using ll = long long;

struct S {
    mint a, b;
    mint f(mint x) { return a * x + b; }
};
S op(S l, S r) { return S{l.a * r.a, l.b * r.a + r.b}; }
S e() { return S{1, 0}; }

int main() {
    ll n, q;
    cin >> n >> q;

    DynamicSegTree<S, op, e, 30> seg;
    while(q--) {
        int t;
        cin >> t;
        if(t == 0) {
            ll p, c, d;
            cin >> p >> c >> d;
            seg.set(p, S{c, d});
        } else {
            ll l, r, x;
            cin >> l >> r >> x;
            cout << seg.prod(l, r).f(x).x << endl;
        }
    }
}

Back to top page