library

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

---

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

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

• View this file on GitHub
• Last update: 2025-02-04 02:11:42+09:00
• Include: #include "DataStructure/dynamicrectsum.hpp"

Depends on

• Binary Indexed Tree (DataStructure/bit.hpp)
• Static Rectangle Sum (DataStructure/staticrectsum.hpp)

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){
        T res=0;
        for(;i;i-=(i&-i))res+=val[i];
        return res;
    }
    T sum(int L,int R){return sum(R)-sum(L);} // [L,R)

    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.u, q.d) * 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