test/library_checker/data_structure/point_set_range_composite_large_array.test.cpp

• View this file on GitHub
• Last update: 2025-01-09 22:07:23+09:00
• Problem: https://judge.yosupo.jp/problem/point_set_range_composite_large_array

Depends on

• lib/data_structure/segment_tree_func.hpp
• ModInt (lib/math/modint.hpp)
• Compression (座標圧縮) (lib/others/compression.hpp)

Code

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

#include <iostream>
#include <vector>
#include <tuple>

#include "../../../lib/data_structure/segment_tree_func.hpp"
#include "../../../lib/math/modint.hpp"
#include "../../../lib/others/compression.hpp"

using namespace std;

using mint = ModInt<998244353>;
using F = pair<mint, mint>;

F op(F a, F b){
    return {a.first * b.first, a.second * b.first + b.second};
}

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

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

    int n, q; cin >> n >> q;
    using T = tuple<int, int, int, int>;
    vector<T> query(q);
    vector<int> c;
    for(int i = 0; i < q; i++){
        int t, x, y, z; cin >> t >> x >> y >> z;
        query[i] = {t, x, y, z};
        if(t == 0){
            c.push_back(x);
        }else{
            c.push_back(x);
            c.push_back(y);
        }
    }
    compress<int> comp(c);
    SegTree<F, op, e> seg(comp.size());
    for(int i = 0; i < q; i++){
        auto [t, x, y, z] = query[i];
        if(t == 0){
            seg.update(comp.get(x), {y, z});
        }else{
            F res = seg.query(comp.get(x), comp.get(y));
            cout << res.first * z + res.second << "\n";
        }
    }
}

#line 1 "test/library_checker/data_structure/point_set_range_composite_large_array.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/point_set_range_composite_large_array"

#include <iostream>
#include <vector>
#include <tuple>

#line 2 "lib/data_structure/segment_tree_func.hpp"

#line 4 "lib/data_structure/segment_tree_func.hpp"
#include <cassert>

template <typename T, T (*op)(T, T), T(*e)()>
struct SegTree{
    int _n, n;
    std::vector<T> dat;

    SegTree(int _n) : _n(_n) {
        int x = 1;
        while(_n > x){
            x *= 2;
        }
        n = x;
        dat.resize(n * 2);
        for(int i = 0; i < n * 2; ++i){
            dat[i] = e();
        }
    }
    SegTree(std::vector<T> &v) : _n((int) v.size()) {
        int x = 1;
        while((int) v.size() > x){
            x *= 2;
        }
        n = x;
        dat.resize(n * 2);
        for(int i = 0; i < n; ++i){
            set(i, (i < (int) v.size() ? v[i] : e()));
        }
        build();
    }

private:
    void set(int i, const T &x){ dat[i + n] = x; }

    void build(){
        for(int k = n - 1; k >= 1; k--) dat[k] = op(dat[k * 2], dat[k * 2 + 1]);
    }

public:
    T get(int i) const {
        assert(0 <= i && i < n);
        return dat[i + n];
    }

    void update(int i, const T &x){
        assert(0 <= i && i < n);
        i += n;
        dat[i] = x;
        while(i > 0){
            i >>= 1;  // parent
            dat[i] = op(dat[i * 2], dat[i * 2 + 1]);
        }
    }

    T query(int a, int b){
        assert(0 <= a && a <= b && b <= n);
        T vl = e();
        T vr = e();
        int l = a + n;
        int r = b + n;
        while(l < r){
            if(l & 1) vl = op(vl, dat[l++]);
            if(r & 1) vr = op(dat[--r], vr);
            l >>= 1;
            r >>= 1;
        }
        return op(vl, vr);
    }

    template <class F>
    int max_right(int l, F f) const {
        assert(0 <= l && l <= _n);
        assert(f(e()));
        if(l == _n) return _n;
        l += n;
        T sm = e();
        do{
            while(l % 2 == 0) l >>= 1;
            if(!f(op(sm, dat[l]))){
                while(l < n){
                    l = (2 * l);
                    if(f(op(sm, dat[l]))){
                        sm = op(sm, dat[l]);
                        l++;
                    }
                }
                return l - n;
            }
            sm = op(sm, dat[l]);
            l++;
        }while((l & -l) != l);
        return _n;
    }

    template <class F>
    int min_left(int r, F f) const {
        assert(0 <= r && r <= _n);
        assert(f(e()));
        if(r == 0) return 0;
        r += n;
        T sm = e();
        do{
            r--;
            while(r > 1 && (r % 2)) r >>= 1;
            if(!f(op(dat[r], sm))){
                while(r < n){
                    r = (2 * r + 1);
                    if(f(op(dat[r], sm))){
                        sm = op(dat[r], sm);
                        r--;
                    }
                }
                return r + 1 - n;
            }
            sm = op(dat[r], sm);
        }while((r & -r) != r);
        return 0;
    }
};
#line 2 "lib/math/modint.hpp"

#line 5 "lib/math/modint.hpp"

/**
 * @brief ModInt
 * @docs docs/math/modint.md
 */

template <long long Modulus>
struct ModInt{
    long long val;
    static constexpr int mod() { return Modulus; }
    constexpr ModInt(const long long _val = 0) noexcept : val(_val) {
        normalize();
    }
    void normalize(){
        val = (val % Modulus + Modulus) % Modulus;
    }
    inline ModInt &operator+=(const ModInt &rhs) noexcept {
        if(val += rhs.val, val >= Modulus) val -= Modulus;
        return *this;
    }
    inline ModInt &operator-=(const ModInt &rhs) noexcept {
        if(val -= rhs.val, val < 0) val += Modulus;
        return *this;
    }
    inline ModInt &operator*=(const ModInt &rhs) noexcept {
        val = val * rhs.val % Modulus;
        return *this;
    }
    inline ModInt &operator/=(const ModInt &rhs) noexcept {
        val = val * inv(rhs.val).val % Modulus;
        return *this;
    }
    inline ModInt &operator++() noexcept {
        if(++val >= Modulus) val -= Modulus;
        return *this;
    }
    inline ModInt operator++(int) noexcept {
        ModInt t = val;
        if(++val >= Modulus) val -= Modulus;
        return t;
    }
    inline ModInt &operator--() noexcept {
        if(--val < 0) val += Modulus;
        return *this;
    }
    inline ModInt operator--(int) noexcept {
        ModInt t = val;
        if(--val < 0) val += Modulus;
        return t;
    }
    inline ModInt operator-() const noexcept { return (Modulus - val) % Modulus; }
    inline ModInt inv(void) const { return inv(val); }
    ModInt pow(long long n) const {
        assert(0 <= n);
        ModInt x = *this, r = 1;
        while(n){
            if(n & 1) r *= x;
            x *= x;
            n >>= 1;
        }
        return r;
    }
    ModInt inv(const long long n) const {
        long long a = n, b = Modulus, u = 1, v = 0;
        while(b){
            long long t = a / b;
            a -= t * b; std::swap(a, b);
            u -= t * v; std::swap(u, v);
        }
        u %= Modulus;
        if(u < 0) u += Modulus;
        return u;
    }
    friend inline ModInt operator+(const ModInt &lhs, const ModInt &rhs) noexcept { return ModInt(lhs) += rhs; }
    friend inline ModInt operator-(const ModInt &lhs, const ModInt &rhs) noexcept { return ModInt(lhs) -= rhs; }
    friend inline ModInt operator*(const ModInt &lhs, const ModInt &rhs) noexcept { return ModInt(lhs) *= rhs; }
    friend inline ModInt operator/(const ModInt &lhs, const ModInt &rhs) noexcept { return ModInt(lhs) /= rhs; }
    friend inline bool operator==(const ModInt &lhs, const ModInt &rhs) noexcept { return lhs.val == rhs.val; }
    friend inline bool operator!=(const ModInt &lhs, const ModInt &rhs) noexcept { return lhs.val != rhs.val; }
    friend inline std::istream &operator>>(std::istream &is, ModInt &x) noexcept {
        is >> x.val;
        x.normalize();
        return is;
    }
    friend inline std::ostream &operator<<(std::ostream &os, const ModInt &x) noexcept { return os << x.val; }
};
#line 2 "lib/others/compression.hpp"

/**
 * @brief Compression (座標圧縮)
 * @docs docs/others/compression.md
 */

#line 9 "lib/others/compression.hpp"
#include <algorithm>

template <typename T>
struct compress{
    std::vector<T> sorted;
    std::vector<int> compressed;

    compress(const std::vector<T> &vec){
        int n = vec.size();
        compressed.resize(n);
        for(T x : vec){
            sorted.emplace_back(x);
        }
        std::sort(sorted.begin(), sorted.end());
        sorted.erase(std::unique(sorted.begin(), sorted.end()), sorted.end());
        for(int i = 0; i < n; ++i){
            compressed[i] = std::lower_bound(sorted.begin(), sorted.end(), vec[i]) - sorted.begin();
        }
    }

    int get(const T &x) const{
        return std::lower_bound(sorted.begin(), sorted.end(), x) - sorted.begin();
    }

    T inv(const int x) const{
        return sorted[x];
    }

    size_t size() const{
        return sorted.size();
    }

    std::vector<int> getCompressed() const{
        return compressed;
    }
};
#line 10 "test/library_checker/data_structure/point_set_range_composite_large_array.test.cpp"

using namespace std;

using mint = ModInt<998244353>;
using F = pair<mint, mint>;

F op(F a, F b){
    return {a.first * b.first, a.second * b.first + b.second};
}

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

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

    int n, q; cin >> n >> q;
    using T = tuple<int, int, int, int>;
    vector<T> query(q);
    vector<int> c;
    for(int i = 0; i < q; i++){
        int t, x, y, z; cin >> t >> x >> y >> z;
        query[i] = {t, x, y, z};
        if(t == 0){
            c.push_back(x);
        }else{
            c.push_back(x);
            c.push_back(y);
        }
    }
    compress<int> comp(c);
    SegTree<F, op, e> seg(comp.size());
    for(int i = 0; i < q; i++){
        auto [t, x, y, z] = query[i];
        if(t == 0){
            seg.update(comp.get(x), {y, z});
        }else{
            F res = seg.query(comp.get(x), comp.get(y));
            cout << res.first * z + res.second << "\n";
        }
    }
}

Back to top page