コンテンツにスキップ

ABC477 F - Count Cells in a Window

サイト
AtCoder
コンテスト
ABC477
問題
F - Count Cells in a Window
難易度
-

NN 行 MM 列のグリッドがあり、上から ii 行目は左から LiL_i 列目から RiR_i 列目までのマスが黒、それ以外のマスが白です。QQ 個のクエリで A,B,C,DA, B, C, D が与えられるので、AA 行目から BB 行目、CC 列目から DD 列目までの長方形に含まれる黒いマスの個数をそれぞれ答える問題です(1≤N,M,Q≤2×1051 \le N, M, Q \le 2 \times 10^5)。

上から kk 行目までのうち、CC 列目から DD 列目までにある黒いマスの個数を f(k)f(k) とすると、クエリの答えは f(B)−f(A−1)f(B) - f(A - 1) です。

列ごとの黒いマスの個数を表す長さ MM の配列を用意し、11 行目から順に、ii 行目を加えるたびに LiL_i 列目から RiR_i 列目までに 11 を足していきます。kk 行目まで加えたところでこの配列の CC 列目から DD 列目までの和をとれば、f(k)f(k) が求まります。

そこで、各クエリを「A−1A - 1 行目まで加えたときに ff を引く」と「BB 行目まで加えたときに ff を足す」の 2 つに分け、行の順にまとめて処理します(クエリを先に全部読んでおくので、オフラインで解くことになります)。

必要な操作は、配列の区間に 11 を足すことと、区間の和を求めることです。これは区間加算・区間和の遅延評価セグメント木か、BIT を 2 本使う方法で、どちらも O(log⁡M)O(\log M) でできます。クエリを行の順にソートするのとあわせて、全体の計算量は O(N+M+Qlog⁡Q+(N+Q)log⁡M)O(N + M + Q \log Q + (N + Q) \log M) です。

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) は長さ 22 の配列を NN 個読み込むマクロです。列は 0 始まりの半開区間 [Li−1,Ri)[L_i - 1, R_i)、[C−1,D)[C - 1, D) で扱っています。

tmp には各クエリを (行数, C, D, 符号, クエリ番号) の 2 つに分けて入れ、行数の順にソートしています。k はすでに加えた行数で、行数 x のクエリを処理する前に x 行目まで加えます。RAddSumQ は区間加算・区間和の遅延評価セグメント木で、apply(l, r, 1) で区間に 11 を足し、prod(c, d) で区間の和を求めています。

使用ライブラリ:cpp_include@6519da7