library
library copied to clipboard
Published
20 hours ago •
ei1333
ei1333
Static Rectangle Add Rectangle Sum
なんか手元にたまたまあったんですが、これ？
template< typename Coordinate, typename Weight >
class static_point_add_rectangle_sum {
vector< Coordinate > xs, ys;
vector< pair< pair< Coordinate, Coordinate >, Weight > > ws;
size_t k = 0;
vector< pair< pair< Coordinate, Coordinate >, pair< size_t, Weight > > > qs;
public:
vector< Weight > calculate_queries() {
sort(xs.begin(), xs.end());
xs.erase(unique(xs.begin(), xs.end()), xs.end());
sort(ys.begin(), ys.end());
ys.erase(unique(ys.begin(), ys.end()), ys.end());
sort(ws.begin(), ws.end());
sort(qs.begin(), qs.end());
vector< Weight > res(k);
fenwick_tree< Weight > fs(ys.size());
size_t idx = 0;
for (auto &[p, q] : qs) {
while (idx != ws.size() and ws[idx].first <= p) {
int y = ws[idx].first.second;
y = lower_bound(ys.begin(), ys.end(), y) - ys.begin();
fs.add(y, ws[idx].second);
idx++;
}
size_t y = lower_bound(ys.begin(), ys.end(), p.second) - ys.begin();
res[q.first] += q.second * fs.sum(0, y);
}
return res;
}
void add_point(Coordinate x, Coordinate y, Weight w) {
xs.emplace_back(x);
ys.emplace_back(y);
ws.emplace_back(make_pair(x, y), w);
}
// total weight of (left, right] and (lower, upper] point
void query(Coordinate left, Coordinate right, Coordinate lower, Coordinate upper) {
xs.emplace_back(left);
xs.emplace_back(right);
ys.emplace_back(lower);
ys.emplace_back(upper);
qs.emplace_back(make_pair(left, lower), make_pair(k, 1));
qs.emplace_back(make_pair(right, upper), make_pair(k, 1));
qs.emplace_back(make_pair(left, upper), make_pair(k, -1));
qs.emplace_back(make_pair(right, lower), make_pair(k, -1));
k++;
}
};
