ABC477 F - Count Cells in a Window
行 列のグリッドがあり、上から 行目は左から 列目から 列目までのマスが黒、それ以外のマスが白です。 個のクエリで が与えられるので、 行目から 行目、 列目から 列目までの長方形に含まれる黒いマスの個数をそれぞれ答える問題です()。
上から 行の差に分ける
Section titled “上から kkk 行の差に分ける”上から 行目までのうち、 列目から 列目までにある黒いマスの個数を とすると、クエリの答えは です。
列ごとの黒いマスの個数を表す長さ の配列を用意し、 行目から順に、 行目を加えるたびに 列目から 列目までに を足していきます。 行目まで加えたところでこの配列の 列目から 列目までの和をとれば、 が求まります。
そこで、各クエリを「 行目まで加えたときに を引く」と「 行目まで加えたときに を足す」の 2 つに分け、行の順にまとめて処理します(クエリを先に全部読んでおくので、オフラインで解くことになります)。
区間加算・区間和
Section titled “区間加算・区間和”必要な操作は、配列の区間に を足すことと、区間の和を求めることです。これは区間加算・区間和の遅延評価セグメント木か、BIT を 2 本使う方法で、どちらも でできます。クエリを行の順にソートするのとあわせて、全体の計算量は です。
C++
#include "shogo-library/base/all"#include "shogo-library/data_structures/lazy-segtree.hpp"#include "shogo-library/utility/container_func.hpp"
void solve() { LL(N, M, Q); VAL(LR, N, 2); VAL(ABCD, Q, 4); val<5> tmp; for (auto &[l, r] : LR) l--; rep(i, Q) { auto &[a, b, c, d] = ABCD[i]; a--, c--; tmp.push_back({a, c, d, -1, i}); tmp.push_back({b, c, d, 1, i}); } sort(tmp); RAddSumQ<ll> seg(M); ll k = 0; vl ans(Q); for (auto [x, c, d, y, i] : tmp) { while (k < x) { auto [l, r] = LR[k++]; seg.apply(l, r, 1); } ans[i] += y * seg.prod(c, d); } rep(i, Q) print(ans[i]);}
int main() { std::cin.tie(nullptr); std::ios_base::sync_with_stdio(false); solve();}VAL(LR, N, 2) は長さ の配列を 個読み込むマクロです。列は 0 始まりの半開区間 、 で扱っています。
tmp には各クエリを (行数, C, D, 符号, クエリ番号) の 2 つに分けて入れ、行数の順にソートしています。k はすでに加えた行数で、行数 x のクエリを処理する前に x 行目まで加えます。RAddSumQ は区間加算・区間和の遅延評価セグメント木で、apply(l, r, 1) で区間に を足し、prod(c, d) で区間の和を求めています。
使用ライブラリ:cpp_include@6519da7