Static rectangle add rectangle sum （矩形一様加算・矩形総和取得）
(data_structure/rectangle_add_rectangle_sum.hpp)

View this file on GitHub
Last update: 2022-07-05 20:49:30+09:00
Include: #include "data_structure/rectangle_add_rectangle_sum.hpp"

以下の処理を $O(n \log n)$ （$n$ は総クエリ数）で行う．

事前矩形加算クエリ：$x_l \le x < x_r, y_l \le y < y_r$ を満たす各格子点 $(x, y)$ に重み $v$ を加算する．
矩形和取得クエリ：$x_l \le x < x_r, y_l \le y < y_r$ を満たす各格子点 $(x, y)$ の重みの総和を取得する．

原理

単一の矩形和取得クエリ $(x_l, x_r, y_l, y_r)$ によって得られる値を $f(x_l, x_r, y_l, y_r)$ と表記すると，

$\displaystyle f(x_l, x_r, y_l, y_r) = f(-\infty, x_r, -\infty, y_r) - f(-\infty, x_l, -\infty, y_r) - f(-\infty, x_r, -\infty, y_l) + f(-\infty, x_l, -\infty, y_l) $

が成立する．よって，矩形和取得クエリとして $x_l = y_l = -\infty$ のものにだけ対応できればよい．

同様に，$(x_l, x_r, y_l, y_r)$ 型の矩形加算クエリも，$(x_, \infty, y_, \infty)$ 型のクエリの重ね合わせとして表現できる．

$(x_a, \infty, y_a, \infty)$ 型の矩形加算クエリの，$(-\infty, x_s, -\infty, y_s)$ 型の矩形和取得クエリへの寄与を考えたい．この寄与は $x_a < x_s$ または $y_a < y_s$ を満たさない場合ゼロとなる．両方を満たす場合は重みの寄与は $(x_s - x_a)(y_s - y_a)$ 倍される．

$y$ 軸方向のデータの管理に Fenwick tree を使用して $x$ 軸方向に平面走査を行うことで，$x_a < x_s$ 及び $y_a < y_s$ の制約の考慮が可能である．各矩形加算クエリに対して Fenwick tree を更新し，矩形和取得クエリ $(x_s, y_s)$ に対して Fenwick tree の和を求めればよい．このとき，取得すべき重みは $x_s, y_s$ についてそれぞれ $1$ 次の項と $0$ 次の項に展開できるから，それぞれの項を管理する $2^2 = 4$ 本の Fenwick tree を持つことで $x_s, y_s$ に関する多項式の形をした重みの寄与が適切に計算できる．

使用方法

RectangleAddRectangleSum<int, mint> rect_sum;

rect_sum.add_rectangle(xl, xr, yl, yr, mint(w));  // Add w to each of [xl, xr) * [yl, yr)

rect_sum.add_query(l, r, d, u); // Get sum of [l, r) * [d, u)

vector<mint> ret = rect_sum.solve();

問題例

Codeforces Round #789 (Div. 1) E. Tokitsukaze and Beautiful Subsegments

Depends on

Binary indexed tree / Fenwick tree （BIT・フェニック木） (segmenttree/binary_indexed_tree.hpp)

Verified with

Code

#pragma once
#include "../segmenttree/binary_indexed_tree.hpp"
#include <algorithm>
#include <tuple>
#include <vector>

// Static rectangle add rectangle sum
// Calculate sums of rectangular weights inside the given rectangles
// Complexity: O(q log q), q = # of rectangles / queries
template <class Int, class T> class RectangleAddRectangleSum {
    struct AddQuery {
        Int xl, xr, yl, yr;
        T val;
    };
    struct SumQuery {
        Int xl, xr, yl, yr;
    };
    std::vector<AddQuery> add_queries;
    std::vector<SumQuery> sum_queries;

public:
    RectangleAddRectangleSum() = default;

    // A[x][y] += val for (x, y) in [xl, xr) * [yl, yr)
    void add_rectangle(Int xl, Int xr, Int yl, Int yr, T val) {
        add_queries.push_back(AddQuery{xl, xr, yl, yr, val});
    }

    // Get sum of A[x][y] for (x, y) in [xl, xr) * [yl, yr)
    void add_query(Int xl, Int xr, Int yl, Int yr) {
        sum_queries.push_back(SumQuery{xl, xr, yl, yr});
    }

    std::vector<T> solve() const {
        std::vector<Int> ys;
        for (const auto &a : add_queries) {
            ys.push_back(a.yl);
            ys.push_back(a.yr);
        }
        std::sort(ys.begin(), ys.end());
        ys.erase(std::unique(ys.begin(), ys.end()), ys.end());

        const int Y = ys.size();

        std::vector<std::tuple<Int, int, int>> ops;
        for (int q = 0; q < int(sum_queries.size()); ++q) {
            ops.emplace_back(sum_queries[q].xl, 0, q);
            ops.emplace_back(sum_queries[q].xr, 1, q);
        }
        for (int q = 0; q < int(add_queries.size()); ++q) {
            ops.emplace_back(add_queries[q].xl, 2, q);
            ops.emplace_back(add_queries[q].xr, 3, q);
        }
        std::sort(ops.begin(), ops.end());

        BIT<T> b00(Y), b01(Y), b10(Y), b11(Y);
        std::vector<T> ret(sum_queries.size());
        for (auto o : ops) {
            int qtype = std::get<1>(o), q = std::get<2>(o);
            if (qtype >= 2) {
                const AddQuery &query = add_queries.at(q);
                int i = std::lower_bound(ys.begin(), ys.end(), query.yl) - ys.begin();
                int j = std::lower_bound(ys.begin(), ys.end(), query.yr) - ys.begin();
                T x = std::get<0>(o);
                T yi = query.yl, yj = query.yr;
                if (qtype & 1) std::swap(i, j), std::swap(yi, yj);

                b00.add(i, x * yi * query.val);
                b01.add(i, -x * query.val);
                b10.add(i, -yi * query.val);
                b11.add(i, query.val);
                b00.add(j, -x * yj * query.val);
                b01.add(j, x * query.val);
                b10.add(j, yj * query.val);
                b11.add(j, -query.val);
            } else {
                const SumQuery &query = sum_queries.at(q);
                int i = std::lower_bound(ys.begin(), ys.end(), query.yl) - ys.begin();
                int j = std::lower_bound(ys.begin(), ys.end(), query.yr) - ys.begin();
                T x = std::get<0>(o);
                T yi = query.yl, yj = query.yr;
                if (qtype & 1) std::swap(i, j), std::swap(yi, yj);

                ret[q] += b00.sum(i) + b01.sum(i) * yi + b10.sum(i) * x + b11.sum(i) * x * yi;
                ret[q] -= b00.sum(j) + b01.sum(j) * yj + b10.sum(j) * x + b11.sum(j) * x * yj;
            }
        }
        return ret;
    }
};

#line 2 "segmenttree/binary_indexed_tree.hpp"
#include <algorithm>
#include <vector>

// CUT begin
// 0-indexed BIT (binary indexed tree / Fenwick tree) (i : [0, len))
template <class T> struct BIT {
    int n;
    std::vector<T> data;
    BIT(int len = 0) : n(len), data(len) {}
    void reset() { std::fill(data.begin(), data.end(), T(0)); }
    void add(int pos, T v) { // a[pos] += v
        pos++;
        while (pos > 0 and pos <= n) data[pos - 1] += v, pos += pos & -pos;
    }
    T sum(int k) const { // a[0] + ... + a[k - 1]
        T res = 0;
        while (k > 0) res += data[k - 1], k -= k & -k;
        return res;
    }

    T sum(int l, int r) const { return sum(r) - sum(l); } // a[l] + ... + a[r - 1]

    template <class OStream> friend OStream &operator<<(OStream &os, const BIT &bit) {
        T prv = 0;
        os << '[';
        for (int i = 1; i <= bit.n; i++) {
            T now = bit.sum(i);
            os << now - prv << ',', prv = now;
        }
        return os << ']';
    }
};
#line 4 "data_structure/rectangle_add_rectangle_sum.hpp"
#include <tuple>
#line 6 "data_structure/rectangle_add_rectangle_sum.hpp"

// Static rectangle add rectangle sum
// Calculate sums of rectangular weights inside the given rectangles
// Complexity: O(q log q), q = # of rectangles / queries
template <class Int, class T> class RectangleAddRectangleSum {
    struct AddQuery {
        Int xl, xr, yl, yr;
        T val;
    };
    struct SumQuery {
        Int xl, xr, yl, yr;
    };
    std::vector<AddQuery> add_queries;
    std::vector<SumQuery> sum_queries;

public:
    RectangleAddRectangleSum() = default;

    // A[x][y] += val for (x, y) in [xl, xr) * [yl, yr)
    void add_rectangle(Int xl, Int xr, Int yl, Int yr, T val) {
        add_queries.push_back(AddQuery{xl, xr, yl, yr, val});
    }

    // Get sum of A[x][y] for (x, y) in [xl, xr) * [yl, yr)
    void add_query(Int xl, Int xr, Int yl, Int yr) {
        sum_queries.push_back(SumQuery{xl, xr, yl, yr});
    }

    std::vector<T> solve() const {
        std::vector<Int> ys;
        for (const auto &a : add_queries) {
            ys.push_back(a.yl);
            ys.push_back(a.yr);
        }
        std::sort(ys.begin(), ys.end());
        ys.erase(std::unique(ys.begin(), ys.end()), ys.end());

        const int Y = ys.size();

        std::vector<std::tuple<Int, int, int>> ops;
        for (int q = 0; q < int(sum_queries.size()); ++q) {
            ops.emplace_back(sum_queries[q].xl, 0, q);
            ops.emplace_back(sum_queries[q].xr, 1, q);
        }
        for (int q = 0; q < int(add_queries.size()); ++q) {
            ops.emplace_back(add_queries[q].xl, 2, q);
            ops.emplace_back(add_queries[q].xr, 3, q);
        }
        std::sort(ops.begin(), ops.end());

        BIT<T> b00(Y), b01(Y), b10(Y), b11(Y);
        std::vector<T> ret(sum_queries.size());
        for (auto o : ops) {
            int qtype = std::get<1>(o), q = std::get<2>(o);
            if (qtype >= 2) {
                const AddQuery &query = add_queries.at(q);
                int i = std::lower_bound(ys.begin(), ys.end(), query.yl) - ys.begin();
                int j = std::lower_bound(ys.begin(), ys.end(), query.yr) - ys.begin();
                T x = std::get<0>(o);
                T yi = query.yl, yj = query.yr;
                if (qtype & 1) std::swap(i, j), std::swap(yi, yj);

                b00.add(i, x * yi * query.val);
                b01.add(i, -x * query.val);
                b10.add(i, -yi * query.val);
                b11.add(i, query.val);
                b00.add(j, -x * yj * query.val);
                b01.add(j, x * query.val);
                b10.add(j, yj * query.val);
                b11.add(j, -query.val);
            } else {
                const SumQuery &query = sum_queries.at(q);
                int i = std::lower_bound(ys.begin(), ys.end(), query.yl) - ys.begin();
                int j = std::lower_bound(ys.begin(), ys.end(), query.yr) - ys.begin();
                T x = std::get<0>(o);
                T yi = query.yl, yj = query.yr;
                if (qtype & 1) std::swap(i, j), std::swap(yi, yj);

                ret[q] += b00.sum(i) + b01.sum(i) * yi + b10.sum(i) * x + b11.sum(i) * x * yi;
                ret[q] -= b00.sum(j) + b01.sum(j) * yj + b10.sum(j) * x + b11.sum(j) * x * yj;
            }
        }
        return ret;
    }
};

Static rectangle add rectangle sum （矩形一様加算・矩形総和取得） (data_structure/rectangle_add_rectangle_sum.hpp)

原理

使用方法

問題例

Depends on

Verified with

Code

Static rectangle add rectangle sum （矩形一様加算・矩形総和取得）
(data_structure/rectangle_add_rectangle_sum.hpp)