src/datastructure/staticrangesum.hpp

• View this file on GitHub
• Last update: 2021-12-30 20:52:19+09:00
• Include: #include "src/datastructure/staticrangesum.hpp"

Depends on

• src/base.hpp

Verified with

• src/staticrangesum_rectangle_sum.test.cpp

Code

#pragma once

#include "base.hpp"

template <class D, class I> struct StaticRangeSum {
    struct P {
        I x, y;
        D val;
    };

    StaticRangeSum(V<P> ps) {
        if (!ps.size()) return;
        sort(ps.begin(), ps.end(), [&](P l, P r) { return l.x < r.x; });
        for (auto p : ps) {
            xs.push_back(p.x);
            ys.push_back(p.y);
        }
        sort(ys.begin(), ys.end());
        ys.erase(unique(ys.begin(), ys.end()), ys.end());

        int n = int(xs.size());
        int m = int(ys.size());

        lg = 1;
        while ((1 << lg) < m) lg++;

        mid = V<int>(lg);
        bits = VV<int>(lg, V<int>(n + 1));
        sums = VV<D>(lg + 1, V<D>(n + 1));

        struct Q {
            int y;
            D val;
        };
        V<Q> v;
        for (auto p : ps) {
            int y = int(lower_bound(ys.begin(), ys.end(), p.y) - ys.begin());
            v.push_back({y, p.val});
        }
        for (int i = 0; i < n; i++) {
            Q q = v[i];
            sums[lg][i + 1] = sums[lg][i] + q.val;
        }
        for (int lv = lg - 1; lv >= 0; lv--) {
            array<V<Q>, 2> nx;
            for (int i = 0; i < n; i++) {
                Q q = v[i];
                bool f = (q.y >> lv) & 1;
                bits[lv][i + 1] = bits[lv][i] + (f ? 0 : 1);
                nx[f].push_back(q);
            }
            mid[lv] = int(nx[0].size());
            v.clear();
            v.insert(v.end(), nx[0].begin(), nx[0].end());
            v.insert(v.end(), nx[1].begin(), nx[1].end());
            for (int i = 0; i < n; i++) {
                Q q = v[i];
                sums[lv][i + 1] = sums[lv][i] + q.val;
            }
        }
    }
    // (low_x <= x < up_x), (low_y <= y < up_y)なる点の重みの総和
    D sum(I low_x, I low_y, I up_x, I up_y) {
        int _lx = int(lower_bound(xs.begin(), xs.end(), low_x) - xs.begin());
        int _ux = int(lower_bound(xs.begin(), xs.end(), up_x) - xs.begin());
        int _ly = int(lower_bound(ys.begin(), ys.end(), low_y) - ys.begin());
        int _uy = int(lower_bound(ys.begin(), ys.end(), up_y) - ys.begin());
        if (_lx >= _ux || _ly >= _uy) return D(0);
        return sum(_lx, _ux, _uy) - sum(_lx, _ux, _ly);
    }

  private:
    int lg;
    V<I> xs, ys;

    V<int> mid;
    VV<int> bits;
    VV<D> sums;
    D sum(int l, int r, int u) {
        if (u == (1 << lg)) return sums[lg][r] - sums[lg][l];
        D ans = 0;
        for (int lv = lg - 1; lv >= 0; lv--) {
            bool f = (u >> lv) & 1;
            int l0 = bits[lv][l], r0 = bits[lv][r];
            if (f) {
                ans += sums[lv][r0] - sums[lv][l0];
                l = l - l0 + mid[lv];
                r = r - r0 + mid[lv];
            } else {
                l = l0;
                r = r0;
            }
        }
        return ans;
    }
};

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.10.1/x64/lib/python3.10/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
  File "/opt/hostedtoolcache/Python/3.10.1/x64/lib/python3.10/site-packages/onlinejudge_verify/languages/cplusplus.py", line 187, in bundle
    bundler.update(path)
  File "/opt/hostedtoolcache/Python/3.10.1/x64/lib/python3.10/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 401, in update
    self.update(self._resolve(pathlib.Path(included), included_from=path))
  File "/opt/hostedtoolcache/Python/3.10.1/x64/lib/python3.10/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 260, in _resolve
    raise BundleErrorAt(path, -1, "no such header")
onlinejudge_verify.languages.cplusplus_bundle.BundleErrorAt: base.hpp: line -1: no such header

Back to top page