library

This documentation is automatically generated by online-judge-tools/verification-helper

Project maintained by tko919 Hosted on GitHub Pages — Theme by mattgraham

:warning: Dynamic Point Add Rectangle Sum
(DataStructure/dynamicrectsum.hpp)

Depends on

Code

#pragma once
#include "DataStructure/staticrectsum.hpp"

template <typename XY, typename T> struct DynamicPointAddRectangleSum {
    using Point = tuple<XY, XY, T>;
    using Query = tuple<XY, XY, XY, XY>;
    vector<variant<Point, Query>> que;
    DynamicPointAddRectangleSum() {}
    void add(XY x, XY y, T w) {
        que.push_back(Point{x, y, w});
    }
    void query(XY L, XY D, XY R, XY U) {
        que.push_back(Query{L, D, R, U});
    }
    vector<T> run() {
        int Q = SZ(que);
        vector<int> isq(Q);
        vector<int> pos(Q);
        int ptr = 0;
        rep(i, 0, Q) if (holds_alternative<Query>(que[i])) {
            isq[i] = 1;
            pos[i] = ptr++;
        }
        vector<T> ret(ptr);
        auto rec = [&](auto &rec, int L, int R) -> void {
            if (L + 1 >= R)
                return;
            int mid = (L + R) >> 1;
            rec(rec, L, mid);
            rec(rec, mid, R);
            StaticRectangleSum<XY, T> buf;
            rep(k, L, mid) if (!isq[k]) {
                XY x, y;
                T w;
                tie(x, y, w) = get<Point>(que[k]);
                buf.add(x, y, w);
            }
            rep(k, mid, R) if (isq[k]) {
                XY L, D, R, U;
                tie(L, D, R, U) = get<Query>(que[k]);
                buf.query(L, D, R, U);
            }
            auto sub = buf.run();
            ptr = 0;
            rep(k, mid, R) if (isq[k]) {
                ret[pos[k]] += sub[ptr++];
            }
        };
        rec(rec, 0, Q);
        return ret;
    }
};

/**
 * @brief Dynamic Point Add Rectangle Sum
 */
#line 2 "DataStructure/bit.hpp"

template <typename T> struct BIT {
    int n;
    T all = 0;
    vector<T> val;
    BIT(int _n = 0) : n(_n), val(_n + 10) {}
    void clear() {
        val.assign(n + 10, 0);
        all = T();
    }
    void add(int i, T x) {
        for (i++; i <= n; i += (i & -i))
            val[i] = val[i] + x;
        all += x;
    }
    T sum(int i) {
        i = clamp(i, 0, n);
        T res = 0;
        for (; i; i -= (i & -i))
            res += val[i];
        return res;
    }
    // [L,R)

    T sum(int L, int R) {
        if (L > R)
            return T(0);
        return sum(R) - sum(L);
    }
    int lower_bound(T x) {
        int ret = 0, len = 1;
        while (2 * len <= n)
            len <<= 1;
        for (; len >= 1; len >>= 1) {
            if (ret + len <= n and val[ret + len] < x) {
                ret += len;
                x -= val[ret];
            }
        }
        return ret;
    }
};

/**
 * @brief Binary Indexed Tree
 */
#line 3 "DataStructure/staticrectsum.hpp"

template <typename XY, typename T> struct StaticRectangleSum {
    struct P {
        XY x, y;
        T w;
    };
    struct Rect {
        XY l, d, r, u;
    };
    struct Q {
        XY x, d, u;
        int id, inv;
    };
    vector<P> plus;
    vector<Rect> que;
    StaticRectangleSum() {}
    void add(XY x, XY y, T w) {
        plus.push_back({x, y, w});
    }
    void query(XY l, XY d, XY r, XY u) {
        que.push_back({l, d, r, u});
    }
    vector<T> run() {
        ll n = plus.size(), q = que.size();
        sort(ALL(plus), [](P &p, P &q) { return p.y < q.y; });
        vector<XY> ys;
        rep(i, 0, n) ys.push_back(plus[i].y);
        ys.erase(unique(ALL(ys)), ys.end());
        rep(i, 0, n) plus[i].y = lower_bound(ALL(ys), plus[i].y) - ys.begin();
        vector<Q> qs;
        rep(i, 0, q) {
            auto &[l, d, r, u] = que[i];
            d = lower_bound(ALL(ys), d) - ys.begin();
            u = lower_bound(ALL(ys), u) - ys.begin();
            qs.push_back({l, d, u, i, -1});
            qs.push_back({r, d, u, i, 1});
        }
        sort(ALL(plus), [](P &p, P &q) { return p.x < q.x; });
        sort(ALL(qs), [](Q &p, Q &q) { return p.x < q.x; });
        vector<T> res(q);
        int k = 0;
        BIT<T> bit(ys.size());
        for (auto &q : qs) {
            while (k < n and plus[k].x < q.x) {
                bit.add(plus[k].y, plus[k].w);
                k++;
            }
            res[q.id] += bit.sum(q.d, q.u) * q.inv;
        }
        return res;
    }
};

/**
 * @brief Static Rectangle Sum
 */
#line 3 "DataStructure/dynamicrectsum.hpp"

template <typename XY, typename T> struct DynamicPointAddRectangleSum {
    using Point = tuple<XY, XY, T>;
    using Query = tuple<XY, XY, XY, XY>;
    vector<variant<Point, Query>> que;
    DynamicPointAddRectangleSum() {}
    void add(XY x, XY y, T w) {
        que.push_back(Point{x, y, w});
    }
    void query(XY L, XY D, XY R, XY U) {
        que.push_back(Query{L, D, R, U});
    }
    vector<T> run() {
        int Q = SZ(que);
        vector<int> isq(Q);
        vector<int> pos(Q);
        int ptr = 0;
        rep(i, 0, Q) if (holds_alternative<Query>(que[i])) {
            isq[i] = 1;
            pos[i] = ptr++;
        }
        vector<T> ret(ptr);
        auto rec = [&](auto &rec, int L, int R) -> void {
            if (L + 1 >= R)
                return;
            int mid = (L + R) >> 1;
            rec(rec, L, mid);
            rec(rec, mid, R);
            StaticRectangleSum<XY, T> buf;
            rep(k, L, mid) if (!isq[k]) {
                XY x, y;
                T w;
                tie(x, y, w) = get<Point>(que[k]);
                buf.add(x, y, w);
            }
            rep(k, mid, R) if (isq[k]) {
                XY L, D, R, U;
                tie(L, D, R, U) = get<Query>(que[k]);
                buf.query(L, D, R, U);
            }
            auto sub = buf.run();
            ptr = 0;
            rep(k, mid, R) if (isq[k]) {
                ret[pos[k]] += sub[ptr++];
            }
        };
        rec(rec, 0, Q);
        return ret;
    }
};

/**
 * @brief Dynamic Point Add Rectangle Sum
 */
Back to top page