test/library_checker/data_structure/dynamic_point_set_rectangle_affine_rectangle_sum.test.cpp

View this file on GitHub
Last update: 2024-11-20 20:38:44+09:00
Problem: https://judge.yosupo.jp/problem/dynamic_point_set_rectangle_affine_rectangle_sum

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/dynamic_point_set_rectangle_affine_rectangle_sum"
#include <iostream>
#include <vector>
#include <array>

#include "../../../lib/data_structure/kd_tree.hpp"
#include "../../../lib/math/modint.hpp"

using namespace std;

using mint = ModInt<998244353>;

using S = mint;

struct F{
    mint a, b;
};

S op(S l, S r){ return l + r; }

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

S mapping(F l, S r, int size){ return S{r * l.a + size * l.b}; }

F composition(F l, F r){ return F{r.a * l.a, r.b * l.a + l.b}; }

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

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

    int n, q; cin >> n >> q;
    vector<pair<long long, long long>> p(n);
    vector<S> w(n);
    for(int i = 0; i < n; i++){
        cin >> p[i].first >> p[i].second >> w[i];
    }
    using T = array<long long, 7>;
    vector<T> query(q);
    for(int i = 0; i < q; i++){
        int t; cin >> t;
        query[i][0] = t;
        if(t == 0){
            cin >> query[i][1] >> query[i][2] >> query[i][3];
            p.emplace_back(query[i][1], query[i][2]);
            w.emplace_back(query[i][3]);
        }else if(t == 1){
            cin >> query[i][1] >> query[i][2];
        }else if(t == 2){
            cin >> query[i][1] >> query[i][2] >> query[i][3] >> query[i][4];
        }else{
            cin >> query[i][1] >> query[i][2] >> query[i][3] >> query[i][4] >> query[i][5] >> query[i][6];
        }
    }
    KdTree<S, op, e, F, mapping, composition, id> tree(p, w);
    for(int i = n; i < (int) p.size(); i++){
        tree.off(i);
    }
    int cur = n;
    for(int i = 0; i < q; i++){
        int t = query[i][0];
        if(t == 0){
            tree.on(cur);
            tree.update(cur, S{query[i][3]});
            cur++;
        }else if(t == 1){
            tree.update(query[i][1], S{query[i][2]});
        }else if(t == 2){
            long long l = query[i][1], d = query[i][2], r = query[i][3], u = query[i][4];
            cout << tree.query(l, d, r - 1, u - 1) << '\n';
        }else{
            long long l = query[i][1], d = query[i][2], r = query[i][3], u = query[i][4];
            mint a = query[i][5], b = query[i][6];
            tree.apply(l, d, r - 1, u - 1, F{a, b});
        }
    }
}

#line 1 "test/library_checker/data_structure/dynamic_point_set_rectangle_affine_rectangle_sum.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/dynamic_point_set_rectangle_affine_rectangle_sum"
#include <iostream>
#include <vector>
#include <array>

#line 1 "lib/data_structure/kd_tree.hpp"

/**
 * @brief k-d Tree
 * @see https://trap.jp/post/1489/
 */

#include <algorithm>
#include <cassert>
#include <limits>
#include <queue>
#line 12 "lib/data_structure/kd_tree.hpp"

template <class S,
    S(*op)(S, S),
    S(*e)(),
    class F,
    S(*mapping)(F, S, int),
    F(*composition)(F, F),
    F(*id)()>
struct KdTree{
    static constexpr long long INF = std::numeric_limits<long long>::max() / 3;
    static constexpr long long NINF = -INF;

    struct Point{
        long long x, y;
        S val;
        Point() {}
        Point(long long x, long long y, S val) : x(x), y(y), val(val) {}
    };

private:
    struct Node{
        long long min_x, max_x, min_y, max_y;
        int size, index;
        S sum;
        F lazy;
        Node() : min_x(INF), max_x(NINF), min_y(INF), max_y(NINF), size(0), index(-1), sum(e()), lazy(id()) {}
        Node(Point p, int i = -1) : min_x(p.x), max_x(p.x), min_y(p.y), max_y(p.y), size(1), index(i), sum(p.val), lazy(id()) {}
    };

    int _n, size, log;
    std::vector<Node> nodes;
    std::vector<std::pair<S, int>> info;

    void pull(int k){
        if(k == 0) return;
        nodes[k].size = nodes[2 * k].size + nodes[2 * k + 1].size;
        nodes[k].min_x = std::min(nodes[2 * k].min_x, nodes[2 * k + 1].min_x);
        nodes[k].max_x = std::max(nodes[2 * k].max_x, nodes[2 * k + 1].max_x);
        nodes[k].min_y = std::min(nodes[2 * k].min_y, nodes[2 * k + 1].min_y);
        nodes[k].max_y = std::max(nodes[2 * k].max_y, nodes[2 * k + 1].max_y);
        nodes[k].sum = op(nodes[2 * k].sum, nodes[2 * k + 1].sum);
    }

    void all_apply(int k, F f){
        nodes[k].sum = mapping(f, nodes[k].sum, nodes[k].size);
        if(k < size) nodes[k].lazy = composition(f, nodes[k].lazy);
    }

    void push(int k){
        all_apply(2 * k, nodes[k].lazy);
        all_apply(2 * k + 1, nodes[k].lazy);
        nodes[k].lazy = id();
    }

    void build(std::vector<std::pair<Point, int>> &v, int l, int r, bool div_x = true){
        int len = r - l;
        if(len == 1){
            nodes[size + l] = Node(v[l].first, v[l].second);
            if(v[l].second != -1){
                info[v[l].second].second = l;
            }
            return;
        }
        int m = (l + r) / 2;
        if(div_x){
            std::nth_element(v.begin() + l, v.begin() + m, v.begin() + r, [](const std::pair<Point, int> &p, const std::pair<Point, int> &q){
                return p.first.x < q.first.x;
            });
        }else{
            std::nth_element(v.begin() + l, v.begin() + m, v.begin() + r, [](const std::pair<Point, int> &p, const std::pair<Point, int> &q){
                return p.first.y < q.first.y;
            });
        }
        build(v, l, m, !div_x);
        build(v, m, r, !div_x);
    }

    bool inside(long long dx, long long dy, long long dist){
        using i128 = __int128_t;
        return i128(dx) * dx + i128(dy) * dy <= i128(dist) * dist;
    }

public:
    KdTree(const std::vector<std::pair<long long, long long>> &point) : _n(point.size()){
        std::vector<S> val(_n, e());
        init(point, val);
    }

    KdTree(const std::vector<std::pair<long long, long long>> &point, const std::vector<S> &val) : _n(point.size()){
        init(point, val);
    }

    void init(const std::vector<std::pair<long long, long long>> &point, const std::vector<S> &val){
        assert(point.size() == val.size());
        size = 1, log = 0;
        while(size < _n) size *= 2, log++;
        nodes.resize(size * 2);
        info.resize(size, {e(), -1});
        std::vector<std::pair<Point, int>> P(size, {Point{INF, INF, e()}, -1});
        for(int i = 0; i < _n; i++){
            P[i] = {Point(point[i].first, point[i].second, val[i]), i};
        }
        build(P, 0, size);
        for(int i = size - 1; i >= 1; i--) pull(i);
    }

    void on(int k){
        assert(0 <= k && k < _n);
        int p = info[k].second + size;
        for(int i = log; i >= 1; i--) push(p >> i);
        if(nodes[p].size == 1){
            return;
        }
        nodes[p].size = 1;
        nodes[p].sum = info[k].first;
        for(int i = 1; i <= log; i++) pull(p >> i);
    }

    void off(int k){
        assert(0 <= k && k < _n);
        int p = info[k].second + size;
        for(int i = log; i >= 1; i--) push(p >> i);
        info[k].first = nodes[p].sum;
        nodes[p].size = 0;
        nodes[p].sum = e();
        for(int i = 1; i <= log; i++) pull(p >> i);
    }

    void update(int k, const S &x){
        assert(0 <= k && k < _n);
        int p = info[k].second + size;
        for(int i = log; i >= 1; i--) push(p >> i);
        nodes[p].sum = x;
        for(int i = 1; i <= log; i++) pull(p >> i);
    }

    // [sx, tx] x [sy, ty]
    void apply(long long sx, long long sy, long long tx, long long ty, const F &f){
        if(sx > tx || sy > ty) return;
        std::queue<int> que;
        std::vector<int> st;
        que.push(1);
        while(que.size()){
            int p = que.front();
            que.pop();
            if(nodes[p].size == 0 || nodes[p].max_x < sx || tx < nodes[p].min_x || nodes[p].max_y < sy || ty < nodes[p].min_y) continue;
            if(sx <= nodes[p].min_x && nodes[p].max_x <= tx && sy <= nodes[p].min_y && nodes[p].max_y <= ty){
                all_apply(p, f);
                continue;
            }
            push(p);
            que.push(2 * p);
            que.push(2 * p + 1);
            st.push_back(p);
        }
        while(st.size()){
            pull(st.back());
            st.pop_back();
        }
    }

    // [sx, tx] x [sy, ty]
    S query(long long sx, long long sy, long long tx, long long ty){
        if(sx > tx || sy > ty) return e();
        std::queue<int> que;
        que.push(1);
        S res = e();
        while(que.size()){
            int p = que.front();
            que.pop();
            if(nodes[p].size == 0 || nodes[p].max_x < sx || tx < nodes[p].min_x || nodes[p].max_y < sy || ty < nodes[p].min_y) continue;
            if(sx <= nodes[p].min_x && nodes[p].max_x <= tx && sy <= nodes[p].min_y && nodes[p].max_y <= ty){
                res = op(res, nodes[p].sum);
                continue;
            }
            push(p);
            que.push(2 * p);
            que.push(2 * p + 1);
        }
        return res;
    }

    // ユークリッド距離
    template <typename T>
    void getNearbyPoints(long long x, long long y, long long dist, const T &f){
        std::queue<int> que;
        que.push(1);
        while(que.size()){
            int p = que.front();
            que.pop();
            if(nodes[p].size == 0 || !inside(std::clamp(x, nodes[p].min_x, nodes[p].max_x) - x, std::clamp(y, nodes[p].min_y, nodes[p].max_y) - y, dist)) continue;
            if(nodes[p].size == 1){
                f(nodes[p].index);
                continue;
            }
            que.push(2 * p);
            que.push(2 * p + 1);
        }
    }
};
#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 8 "test/library_checker/data_structure/dynamic_point_set_rectangle_affine_rectangle_sum.test.cpp"

using namespace std;

using mint = ModInt<998244353>;

using S = mint;

struct F{
    mint a, b;
};

S op(S l, S r){ return l + r; }

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

S mapping(F l, S r, int size){ return S{r * l.a + size * l.b}; }

F composition(F l, F r){ return F{r.a * l.a, r.b * l.a + l.b}; }

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

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

    int n, q; cin >> n >> q;
    vector<pair<long long, long long>> p(n);
    vector<S> w(n);
    for(int i = 0; i < n; i++){
        cin >> p[i].first >> p[i].second >> w[i];
    }
    using T = array<long long, 7>;
    vector<T> query(q);
    for(int i = 0; i < q; i++){
        int t; cin >> t;
        query[i][0] = t;
        if(t == 0){
            cin >> query[i][1] >> query[i][2] >> query[i][3];
            p.emplace_back(query[i][1], query[i][2]);
            w.emplace_back(query[i][3]);
        }else if(t == 1){
            cin >> query[i][1] >> query[i][2];
        }else if(t == 2){
            cin >> query[i][1] >> query[i][2] >> query[i][3] >> query[i][4];
        }else{
            cin >> query[i][1] >> query[i][2] >> query[i][3] >> query[i][4] >> query[i][5] >> query[i][6];
        }
    }
    KdTree<S, op, e, F, mapping, composition, id> tree(p, w);
    for(int i = n; i < (int) p.size(); i++){
        tree.off(i);
    }
    int cur = n;
    for(int i = 0; i < q; i++){
        int t = query[i][0];
        if(t == 0){
            tree.on(cur);
            tree.update(cur, S{query[i][3]});
            cur++;
        }else if(t == 1){
            tree.update(query[i][1], S{query[i][2]});
        }else if(t == 2){
            long long l = query[i][1], d = query[i][2], r = query[i][3], u = query[i][4];
            cout << tree.query(l, d, r - 1, u - 1) << '\n';
        }else{
            long long l = query[i][1], d = query[i][2], r = query[i][3], u = query[i][4];
            mint a = query[i][5], b = query[i][6];
            tree.apply(l, d, r - 1, u - 1, F{a, b});
        }
    }
}