test/yosupo/point_set_range_sort_range_composite.test.cpp

• View this file on GitHub
• Last update: 2024-01-07 20:09:47+09:00
• Problem: https://judge.yosupo.jp/problem/point_set_range_sort_range_composite

Depends on

• Segment Tree (data-structure/segtree/segment_tree.hpp)
• Sortable Segment Tree (data-structure/segtree/sortable_segment_tree.hpp)
• Mod int (math/modint.hpp)

Code

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

#include <bits/stdc++.h>

#include "../../data-structure/segtree/segment_tree.hpp"
#include "../../data-structure/segtree/sortable_segment_tree.hpp"
#include "../../math/modint.hpp"
using namespace std;

using mint = Modint<998244353>;

struct AffineMonoid {
    using T = pair<mint, mint>;
    static T id() { return {1, 0}; }
    static T op(T a, T b) {
        return {a.first * b.first, a.second * b.first + b.second};
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int N, Q;
    cin >> N >> Q;
    vector<pair<long long, pair<mint, mint>>> kv(N);
    for (int i = 0; i < N; ++i) {
        int p, a, b;
        cin >> p >> a >> b;
        kv[i] = {p, {a, b}};
    }
    SortableSegmentTree<AffineMonoid> st(1e9 + 1, kv);
    for (int i = 0; i < Q; i++) {
        int t;
        cin >> t;
        if (t == 0) {
            int i, p, a, b;
            cin >> i >> p >> a >> b;
            st.update(i, p, {a, b});
        } else if (t == 1) {
            int l, r, x;
            cin >> l >> r >> x;
            auto [a, b] = st.fold(l, r);
            cout << (a * x + b) << "\n";
        } else if (t == 2) {
            int l, r;
            cin >> l >> r;
            st.sort(l, r);
        } else {
            int l, r;
            cin >> l >> r;
            st.sort(l, r, true);
        }
    }
}

#line 1 "test/yosupo/point_set_range_sort_range_composite.test.cpp"
#define PROBLEM \
    "https://judge.yosupo.jp/problem/point_set_range_sort_range_composite"

#include <bits/stdc++.h>

#line 3 "data-structure/segtree/segment_tree.hpp"
#include <bit>
#line 5 "data-structure/segtree/segment_tree.hpp"

template <typename M>
class SegmentTree {
    using T = M::T;

   public:
    SegmentTree() = default;
    explicit SegmentTree(int n) : SegmentTree(std::vector<T>(n, M::id())) {}
    explicit SegmentTree(const std::vector<T>& v)
        : size(std::bit_ceil(v.size())), node(2 * size, M::id()) {
        std::ranges::copy(v, node.begin() + size);
        for (int i = size - 1; i > 0; --i) {
            node[i] = M::op(node[2 * i], node[2 * i + 1]);
        }
    }

    T operator[](int k) const { return node[k + size]; }

    void update(int k, const T& x) {
        k += size;
        node[k] = x;
        while (k >>= 1) node[k] = M::op(node[2 * k], node[2 * k + 1]);
    }

    T fold(int l, int r) const {
        T vl = M::id(), vr = M::id();
        for (l += size, r += size; l < r; l >>= 1, r >>= 1) {
            if (l & 1) vl = M::op(vl, node[l++]);
            if (r & 1) vr = M::op(node[--r], vr);
        }
        return M::op(vl, vr);
    }

    template <typename F>
    int find_first(int l, F cond) const {
        T v = M::id();
        for (l += size; l > 0; l >>= 1) {
            if (l & 1) {
                T nv = M::op(v, node[l]);
                if (cond(nv)) {
                    while (l < size) {
                        nv = M::op(v, node[2 * l]);
                        if (cond(nv)) {
                            l = 2 * l;
                        } else {
                            v = nv, l = 2 * l + 1;
                        }
                    }
                    return l + 1 - size;
                }
                v = nv;
                ++l;
            }
        }
        return -1;
    }

    template <typename F>
    int find_last(int r, F cond) const {
        T v = M::id();
        for (r += size; r > 0; r >>= 1) {
            if (r & 1) {
                --r;
                T nv = M::op(node[r], v);
                if (cond(nv)) {
                    while (r < size) {
                        nv = M::op(node[2 * r + 1], v);
                        if (cond(nv)) {
                            r = 2 * r + 1;
                        } else {
                            v = nv, r = 2 * r;
                        }
                    }
                    return r - size;
                }
                v = nv;
            }
        }
        return -1;
    }

   private:
    int size;
    std::vector<T> node;
};
#line 7 "data-structure/segtree/sortable_segment_tree.hpp"

#line 9 "data-structure/segtree/sortable_segment_tree.hpp"

template <typename M>
class SortableSegmentTree {
    using T = M::T;

   public:
    SortableSegmentTree() = default;
    explicit SortableSegmentTree(long long max_key,
                                 const std::vector<std::pair<long long, T>>& kv)
        : n(kv.size()), max_key(max_key), st_all(n), st_sorted(n), rev(n) {
        for (int k = 0; k < n; ++k) {
            auto [key, val] = kv[k];
            st_sorted[k] = std::make_unique<Node>();
            st_sorted[k]->update(key, val, 0, max_key);
            st_all.update(k, val);
            left.insert(k);
        }
        left.insert(n);
    }

    void update(int k, long long key, const T& val) {
        split(k), split(k + 1);
        st_sorted[k] = std::make_unique<Node>();
        st_sorted[k]->update(key, val, 0, max_key);
        st_all.update(k, val);
    }

    T fold(int l, int r) {
        split(l), split(r);
        return st_all.fold(l, r);
    }

    void sort(int l, int r, bool descending = false) {
        if (r - l <= 1) return;
        split(l), split(r);
        auto it = ++left.find(l);
        while (it != left.end() && *it < r) {
            st_sorted[l] =
                join(std::move(st_sorted[l]), std::move(st_sorted[*it]));
            st_all.update(*it, M::id());
            rev[*it] = false;
            it = left.erase(it);
        }
        if (st_sorted[l]) {
            st_all.update(l, !descending ? st_sorted[l]->val_forward
                                         : st_sorted[l]->val_backward);
            rev[l] = descending;
        }
    }

   private:
    struct Node;
    using node_ptr = std::unique_ptr<Node>;

    struct Node {
        int sz;
        T val_forward, val_backward;
        node_ptr left, right;
        Node()
            : sz(0),
              val_forward(M::id()),
              val_backward(M::id()),
              left(nullptr),
              right(nullptr) {}

        void recalc() {
            int sl = left ? left->sz : 0;
            int sr = right ? right->sz : 0;
            sz = sl + sr;
            T vl_forward = left ? left->val_forward : M::id();
            T vr_forward = right ? right->val_forward : M::id();
            val_forward = M::op(vl_forward, vr_forward);
            T vl_backward = left ? left->val_backward : M::id();
            T vr_backward = right ? right->val_backward : M::id();
            val_backward = M::op(vr_backward, vl_backward);
        }

        void update(long long key, const T& x, long long l, long long r) {
            if (r - l == 1) {
                sz = 1;
                val_forward = val_backward = x;
                return;
            }
            long long m = std::midpoint(l, r);
            if (key < m) {
                if (!left) left = std::make_unique<Node>();
                left->update(key, x, l, m);
            } else {
                if (!right) right = std::make_unique<Node>();
                right->update(key, x, m, r);
            }
            recalc();
        }
    };

    static std::pair<node_ptr, node_ptr> split(node_ptr t, int k) {
        if (k == 0) return {nullptr, std::move(t)};
        if (k == t->sz) return {std::move(t), nullptr};
        int szl = t->left ? t->left->sz : 0;
        auto t2 = std::make_unique<Node>();
        if (k < szl) {
            std::tie(t2->left, t->left) = split(std::move(t->left), k);
            std::swap(t, t2);
        } else {
            std::tie(t->right, t2->right) = split(std::move(t->right), k - szl);
        }
        t->recalc(), t2->recalc();
        return {std::move(t), std::move(t2)};
    }

    static node_ptr join(node_ptr t1, node_ptr t2) {
        if (!t1) return t2;
        if (!t2) return t1;
        t1->left = join(std::move(t1->left), std::move(t2->left));
        t1->right = join(std::move(t1->right), std::move(t2->right));
        t1->recalc();
        return t1;
    }

    int n;
    long long max_key;
    std::set<int> left;
    SegmentTree<M> st_all;
    std::vector<node_ptr> st_sorted;
    std::vector<bool> rev;

    void split(int k) {
        int l = *--left.upper_bound(k);
        if (l == k) return;
        if (!rev[l]) {
            std::tie(st_sorted[l], st_sorted[k]) =
                split(std::move(st_sorted[l]), k - l);
        } else {
            std::tie(st_sorted[k], st_sorted[l]) =
                split(std::move(st_sorted[l]), l + st_sorted[l]->sz - k);
            rev[k] = true;
        }
        left.insert(k);
        if (st_sorted[l]) {
            st_all.update(l, !rev[l] ? st_sorted[l]->val_forward
                                     : st_sorted[l]->val_backward);
        }
        if (st_sorted[k]) {
            st_all.update(k, !rev[k] ? st_sorted[k]->val_forward
                                     : st_sorted[k]->val_backward);
        }
    }
};
#line 4 "math/modint.hpp"

/**
 * @brief Mod int
 */
template <int m>
class Modint {
    using mint = Modint;
    static_assert(m > 0, "Modulus must be positive");

   public:
    static constexpr int mod() { return m; }

    constexpr Modint(long long y = 0) : x(y >= 0 ? y % m : (y % m + m) % m) {}

    constexpr int val() const { return x; }

    constexpr mint& operator+=(const mint& r) {
        if ((x += r.x) >= m) x -= m;
        return *this;
    }
    constexpr mint& operator-=(const mint& r) {
        if ((x += m - r.x) >= m) x -= m;
        return *this;
    }
    constexpr mint& operator*=(const mint& r) {
        x = static_cast<int>(1LL * x * r.x % m);
        return *this;
    }
    constexpr mint& operator/=(const mint& r) { return *this *= r.inv(); }

    constexpr bool operator==(const mint& r) const { return x == r.x; }

    constexpr mint operator+() const { return *this; }
    constexpr mint operator-() const { return mint(-x); }

    constexpr friend mint operator+(const mint& l, const mint& r) {
        return mint(l) += r;
    }
    constexpr friend mint operator-(const mint& l, const mint& r) {
        return mint(l) -= r;
    }
    constexpr friend mint operator*(const mint& l, const mint& r) {
        return mint(l) *= r;
    }
    constexpr friend mint operator/(const mint& l, const mint& r) {
        return mint(l) /= r;
    }

    constexpr mint inv() const {
        int a = x, b = m, u = 1, v = 0;
        while (b > 0) {
            int t = a / b;
            std::swap(a -= t * b, b);
            std::swap(u -= t * v, v);
        }
        return mint(u);
    }

    constexpr mint pow(long long n) const {
        mint ret(1), mul(x);
        while (n > 0) {
            if (n & 1) ret *= mul;
            mul *= mul;
            n >>= 1;
        }
        return ret;
    }

    friend std::ostream& operator<<(std::ostream& os, const mint& r) {
        return os << r.x;
    }

    friend std::istream& operator>>(std::istream& is, mint& r) {
        long long t;
        is >> t;
        r = mint(t);
        return is;
    }

   private:
    int x;
};
#line 9 "test/yosupo/point_set_range_sort_range_composite.test.cpp"
using namespace std;

using mint = Modint<998244353>;

struct AffineMonoid {
    using T = pair<mint, mint>;
    static T id() { return {1, 0}; }
    static T op(T a, T b) {
        return {a.first * b.first, a.second * b.first + b.second};
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int N, Q;
    cin >> N >> Q;
    vector<pair<long long, pair<mint, mint>>> kv(N);
    for (int i = 0; i < N; ++i) {
        int p, a, b;
        cin >> p >> a >> b;
        kv[i] = {p, {a, b}};
    }
    SortableSegmentTree<AffineMonoid> st(1e9 + 1, kv);
    for (int i = 0; i < Q; i++) {
        int t;
        cin >> t;
        if (t == 0) {
            int i, p, a, b;
            cin >> i >> p >> a >> b;
            st.update(i, p, {a, b});
        } else if (t == 1) {
            int l, r, x;
            cin >> l >> r >> x;
            auto [a, b] = st.fold(l, r);
            cout << (a * x + b) << "\n";
        } else if (t == 2) {
            int l, r;
            cin >> l >> r;
            st.sort(l, r);
        } else {
            int l, r;
            cin >> l >> r;
            st.sort(l, r, true);
        }
    }
}

Back to top page