verify/Datastructure_dynamicseg.test.cpp

View this file on GitHub
Last update: 2025-01-10 00:00:54+09:00
Problem: https://judge.yosupo.jp/problem/point_set_range_composite

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/point_set_range_composite"
#include "../Utility/template.hpp"
#include "../Utility/modint.hpp"
#include "../Datastructure/dynamicseg.hpp"
//#include "../Datastructure/segtree.hpp"

using mint = modint998244353;


struct S{
    mint a, b;
    S(){}
    S(mint d, mint t) : a(d), b(t){}
};

S op(S l, S r) {
	S res;
    res.a = l.a * r.a;
    res.b = r.a * l.b + r.b;
    return res;
}

S e() {
	return S(1, 0);
}


int main() {
	int N, Q;
	cin >> N >> Q;
    vec<ll> A(N), B(N);
    rep(i, 0, N) cin >> A[i] >> B[i];

    dynamicsegtree<S, op, e, int> seg(-1000000000, 1000000000);
    //segtree<S, op, e> seg(N);
    rep(i, 0, N) seg.set(i, S(A[i], B[i]));

    while(Q--) {
        int t;
        cin >> t;
        if(t==0) {
            int p, c, d;
            cin >> p >> c >> d;
            seg.set(p, S(c, d));
        }
        else {
            int l, r, x;
            cin >> l >> r >> x;
            auto [a, b] = seg.prod(l ,r);
            cout << (x * a + b).x << '\n';
        }
    }
   

}

#line 1 "verify/Datastructure_dynamicseg.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/point_set_range_composite"
#line 1 "Utility/template.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, s, t) for (ll i = s; i < (ll)(t); i++)
#define rrep(i, s, t) for (ll i = (ll)(t) - 1; i >= (ll)(s); i--)
#define all(x) begin(x), end(x)

#define TT template <typename T>
TT using vec = vector<T>;
template <class T1, class T2> bool chmin(T1 &x, T2 y) {
    return x > y ? (x = y, true) : false;
}
template <class T1, class T2> bool chmax(T1 &x, T2 y) {
    return x < y ? (x = y, true) : false;
}
struct io_setup {
    io_setup() {
        ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
        cout << fixed << setprecision(15);
    }
} io_setup;

/*
@brief verify用テンプレート
*/
#line 1 "Utility/modint.hpp"

// 動的mod : template<int mod> を消して、上の方で変数modを宣言
template <uint32_t mod> struct modint {
    using mm = modint;
    uint32_t x;
    modint() : x(0) {}
    TT modint(T a = 0) : x((ll(a) % mod + mod)) {
        if (x >= mod) x -= mod;
    }

    friend mm operator+(mm a, mm b) {
        a.x += b.x;
        if (a.x >= mod) a.x -= mod;
        return a;
    }
    friend mm operator-(mm a, mm b) {
        a.x -= b.x;
        if (a.x >= mod) a.x += mod;
        return a;
    }

    mm operator-() const { return mod - x; }

    //+と-だけで十分な場合、以下は省略して良いです。

    friend mm operator*(mm a, mm b) { return (uint64_t)(a.x) * b.x; }
    friend mm operator/(mm a, mm b) { return a * b.inv(); }
    friend mm &operator+=(mm &a, mm b) { return a = a + b; }
    friend mm &operator-=(mm &a, mm b) { return a = a - b; }
    friend mm &operator*=(mm &a, mm b) { return a = a * b; }
    friend mm &operator/=(mm &a, mm b) { return a = a * b.inv(); }

    mm inv() const {
        assert(x != 0);
        return pow(mod - 2);
    }
    mm pow(ll y) const {
        mm res = 1;
        mm v = *this;
        while (y) {
            if (y & 1) res *= v;
            v *= v;
            y /= 2;
        }
        return res;
    }

    friend istream &operator>>(istream &is, mm &a) {
        ll t;
        cin >> t;
        a = mm(t);
        return is;
    }

    friend ostream &operator<<(ostream &os, mm a) { return os << a.x; }

    bool operator==(mm a) { return x == a.x; }
    bool operator!=(mm a) { return x != a.x; }

    bool operator<(const mm &a) const { return x < a.x; }
};
using modint998244353 = modint<998244353>;
using modint1000000007 = modint<1'000'000'007>;
/*
@brief modint
*/
#line 1 "Datastructure/dynamicseg.hpp"
template <class S, S (*op)(S, S), S (*e)(), class W> struct dynamicsegtree {
    W  min_pos;
    W  max_pos;
    dynamicsegtree(){} 
    dynamicsegtree(W l, W r) :  min_pos(l), max_pos(r) {};

    private:
        struct Node {
            W p;
            S x;
            S prod;
            Node* l;
            Node* r;
        
            Node(W pos, S v) : p(pos), x(v), prod(v) {
                l = nullptr;
                r = nullptr;
            }
        };
        using np = Node*;
        
        np root = nullptr;

        S val(np v) {
            return v != nullptr ? v -> prod : e(); 
        }

        np apply(np v, W p, S &s, W L, W R) {
            if(!v) {
                v = new Node(p, s);
                return v;
            }
            if(v-> p == p) {
                v -> x = s;
                v -> prod = op(val(v -> l), op(v -> x, val(v -> r)));
                return v;
            }
            
            W M = (L + R) >> 1;

            if(p < M) {
                if(v -> p < p) swap(p, v -> p), swap(s, v -> x);
                v -> l = apply(v -> l, p, s,  L, M);
            }
            else {
                if(v -> p > p) swap(p, v -> p), swap(s, v -> x);
                v -> r = apply(v -> r, p, s, M, R);
            }
            v -> prod = op(val(v -> l), op(v -> x, val(v -> r)));
            return v; 
        }

        S query(np v, W l, W r, W L, W R) {
            if(r <= L || R <= l) return e();
            if(!v) return e();
            if(l <= L && R <= r) return v -> prod;

            W M = (L + R) >> 1;
            S res = query(v -> l, l, r, L, M);
            if(l <= v -> p && v -> p < r) res = op(res, v -> x);
            return op(res, query(v -> r, l, r, M, R));
        }

    public:
        void set(W pos, S s) {
           root = apply(root, pos, s, min_pos, max_pos);
        }

        S  prod(W l, W r) {
            return query(root, l, r, min_pos, max_pos);
        }

};

/*
    @brief 動的セグ木
    @docs doc/dynamicseg.md
        
*/
#line 5 "verify/Datastructure_dynamicseg.test.cpp"
//#include "../Datastructure/segtree.hpp"

using mint = modint998244353;


struct S{
    mint a, b;
    S(){}
    S(mint d, mint t) : a(d), b(t){}
};

S op(S l, S r) {
	S res;
    res.a = l.a * r.a;
    res.b = r.a * l.b + r.b;
    return res;
}

S e() {
	return S(1, 0);
}


int main() {
	int N, Q;
	cin >> N >> Q;
    vec<ll> A(N), B(N);
    rep(i, 0, N) cin >> A[i] >> B[i];

    dynamicsegtree<S, op, e, int> seg(-1000000000, 1000000000);
    //segtree<S, op, e> seg(N);
    rep(i, 0, N) seg.set(i, S(A[i], B[i]));

    while(Q--) {
        int t;
        cin >> t;
        if(t==0) {
            int p, c, d;
            cin >> p >> c >> d;
            seg.set(p, S(c, d));
        }
        else {
            int l, r, x;
            cin >> l >> r >> x;
            auto [a, b] = seg.prod(l ,r);
            cout << (x * a + b).x << '\n';
        }
    }
   

}