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

• View this file on GitHub
• Last update: 2021-04-08 20:15:34+09:00
• Problem: https://judge.yosupo.jp/problem/point_set_range_composite

Depends on

• Segment-Tree (segtree/segment-tree.cpp)

Code

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

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

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

constexpr int mod = 998244353;

struct S {
    int64_t a, b;
    int64_t calc(int64_t x) { return (a * x + b) % mod; }
};

inline S op(S l, S r) { return S{r.a * l.a % mod, (r.a * l.b + r.b) % mod}; }
inline S e() { return S{1, 0}; }

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    int n, q;
    cin >> n >> q;
    vector<S> v;
    v.reserve(n);

    for(int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;
        v.push_back(S{a, b});
    }

    SegmentTree<S, op, e> seg(v);

    for(int i = 0; i < q; i++) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        if(a)
            cout << seg.prod(b, c).calc(d) << "\n";
        else
            seg.set(b, S{c, d});
    }

    return 0;
}

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

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

#line 3 "segtree/segment-tree.cpp"
using namespace std;

// モノイド, 演算, 単位元
template <typename S, S (*op)(S, S), S (*e)()>
class SegmentTree {
private:
    int _n, sz;
    vector<S> data;

    void calc(int k) { data[k] = op(data[k << 1], data[k << 1 | 1]); }

public:
    SegmentTree() = default;
    explicit SegmentTree(int n) : SegmentTree(vector<S>(n, e())) {}
    explicit SegmentTree(const vector<S>& v) : _n(v.size()) {
        sz = 1;
        while(sz < _n) sz <<= 1;
        data.assign(sz << 1, e());
        for(int i = 0; i < _n; i++) data[sz + i] = v[i];
        for(int i = sz - 1; i >= 1; i--) calc(i);
    }

    void set(int p, S x) {
        assert(0 <= p && p < _n);
        p += sz;
        data[p] = x;
        while(p >>= 1) calc(p);
    }

    S get(int p) {
        assert(0 <= p && p < _n);
        return data[p + sz];
    }

    S prod(int l, int r) {
        assert(0 <= l && l <= r && r <= _n);
        S sl = e(), sr = e();
        l += sz;
        r += sz;
        while(l < r) {
            if(l & 1) sl = op(sl, data[l++]);
            if(r & 1) sr = op(data[--r], sr);
            l >>= 1;
            r >>= 1;
        }
        return op(sl, sr);
    }

    S all_prod() { return data[1]; }
};
/*
 * @brief Segment-Tree
 * @docs docs/segment-tree.md
 */
#line 7 "test/yosupo-point-set-range-composite.test.cpp"

constexpr int mod = 998244353;

struct S {
    int64_t a, b;
    int64_t calc(int64_t x) { return (a * x + b) % mod; }
};

inline S op(S l, S r) { return S{r.a * l.a % mod, (r.a * l.b + r.b) % mod}; }
inline S e() { return S{1, 0}; }

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    int n, q;
    cin >> n >> q;
    vector<S> v;
    v.reserve(n);

    for(int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;
        v.push_back(S{a, b});
    }

    SegmentTree<S, op, e> seg(v);

    for(int i = 0; i < q; i++) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        if(a)
            cout << seg.prod(b, c).calc(d) << "\n";
        else
            seg.set(b, S{c, d});
    }

    return 0;
}

Back to top page