https://atcoder.jp/contests/past202107-open/tasks/past202107_n
前提知識
解説
https://atcoder.jp/contests/past202107-open/submissions/24475768
今回の問題は最低限遅延評価セグメントツリーを理解していることが前提となる。
遅延評価セグメントツリーは自分は太古に自作したものをチューニングしながら使っているが、
AtCoder Libraryに素晴らしい実装があるので、そっちをチューニングして使うことをお勧めする。
（1から作るのは勉強になるかもだけど、ややしんどい）
どうやって問題に立ち向かうか
どこから考え始めるかが難しい。
長方形区間の塗りつぶしなので2Dimosかなとも思ったりするが、座圧しても難しい。
ここで、使える手法、平面走査を導入することにする。
平面走査
平面走査とはざっくり書くと、とある座標を小さい方から順番に処理していくような方針を取ることで、
今回紹介する流れで言えばy座標を小さい方から順番に評価していくような方針を取ることで、
それ以前の状態を抽象化というか無視することができ、差分計算によって全体の計算が行える。
かなり方針がざっくりとしすぎていて、何がいいのかというのが分かりにくいかと思う。
なるべく細かく説明してみるが、平面走査の記事を読んでみるのも理解を助けるだろう。
改めて書くと、今回は区間の処理をする際にy座標を小さい方から順番に処理していく方針を取る。
操作を見直す
平面走査を簡単にするために操作を少し見直してみよう。
平面走査をする際にy座標を小さい方からと書いたが、各長方形にはy座標の始点と終点があるので、
どっちを使って大小を取るかというのは少し面倒なので、ちょっと別の考え方をする。
y座標[B[i], D[i]]について反転させるという操作をy=B[i]以降を反転する、y=D[i]以降を反転する
という2操作に分割することにする。
このように分割しても最終的には同じ反転方式となるので、操作の回数が2倍に増えるが、始点と終点で
処理を分ける必要が無く、単純化して操作を見ることができる。
平面走査に戻ろう
y座標を小さい方から処理を行っていくときに、「x座標について反転しているかの配列」を持っておくことにする。
すると、y=prevの状態で作った「x座標について反転しているかの配列」の状態というのは、その次のy=currentまで
その状態が継続していることになるので、「x座標について反転しているかの配列」の反転している区間の総和が
分かっていれば、その総和×前のy座標との差を使うことで黒色である面積が計算できることになる。
上で説明した部分が平面操作で行うときの一番本質的な部分であり、少し細かく説明すると、以下のように図解できる。
y=4 ■■■□□■■■
例えばy=4でこの状態で、次に状態が変化するy座標が6であれば
y=4 ■■■□□■■■
y=5 ■■■□□■■■
のように同じ状態になっているはずなので、反転している区間の総和が分かっていれば、
それに前のy座標との差をかければ黒の面積が求められる。
で、そのあと、そのy座標での反転操作を実施して、例えば以下のようになって
y=4 ■■■□□■■■
y=5 ■■■□□■■■
y=6 □□■□□■■□
次にy=9に操作があるならば、それまでは同じ状態だから、
y=4 ■■■□□■■■
y=5 ■■■□□■■■
y=6 □□■□□■■□
y=7 □□■□□■■□
y=8 □□■□□■■□
となって同様に区間の総和×前のy座標との差で面積計算ができるような感じ。
自分の実装では、getall関数で塗られている区間の総和を取得して、rev関数で区間を反転させている。
ここまで理解できてくれば、やっと折り返し。
残った問題は遅延評価セグメントツリーで解決
残った問題はgetall関数とrev関数の実装である
- getall関数：塗られている区間の総和を計算
- rev関数：とある区間の塗りを反転させる
これは遅延評価セグメントツリーと座標圧縮で実現ができる。
座標圧縮はしないとセグ木に載らないので、ここまでついてこれてる人なら、必要なのは理解できていると思う。
遅延評価セグメントツリーでは、以下のようなルールで更新していけばいい。
- 区間データ dat[k] := その区間で塗られている区間の総和
- 更新関数 comp(a,b) := a+b 普通に区間マージは足せばいい
- 遅延評価データ lazy[k] := 反転するかどうか
- 遅延評価更新関数 setLazy(k,x) := lazy[k] ^= x これはxorで入れ込んでいるので反転させるような実装になる
ここまではよくって、問題が遅延評価データを使って、区間データを更新する部分である。
これにはdat[k] = (dic[r] - dic[l]) - dat[k]とすればいい。
dicは座標圧縮の元の値を保持する配列である。
反転時はその区間の長さに対して塗られていない部分の長さに変換されるので、式に書くとこのような感じになる。
実装…
今回は割と重い実装が2つ重なる問題となる。
どちらも理解していれば、それほど難しくないが、かっちり合わせるのは難しいだろうと思う。
（座圧もあるし…）
頑張ってとしか言えないんですけどね…
vector<int> dic;
template<class V, int NV> struct LazySegTree {
vector<V> dat, lazy; LazySegTree() { dat.resize(NV * 2, def); lazy.resize(NV * 2, ldef); }
void update(int a, int b, V v, int k, int l, int r) {
push(k, l, r); if (r <= a || b <= l) return;
if (a <= l && r <= b) { setLazy(k, v); push(k, l, r); }
else {
update(a, b, v, k * 2, l, (l + r) / 2); update(a, b, v, k * 2 + 1, (l + r) / 2, r);
dat[k] = comp(dat[k * 2], dat[k * 2 + 1]);
}
}
V get(int a, int b, int k, int l, int r) {
push(k, l, r); if (r <= a || b <= l) return def;
if (a <= l && r <= b) return dat[k]; auto x = get(a, b, k * 2, l, (l + r) / 2);
auto y = get(a, b, k * 2 + 1, (l + r) / 2, r); return comp(x, y);
}
void update(int a, int b, V v) { update(a, b, v, 1, 0, NV); }
V get(int a, int b) { return get(a, b, 1, 0, NV); }
const V def = 0, ldef = 0;
V comp(V l, V r) { return l + r; }
void setLazy(int i, V v) { lazy[i] ^= v; }
void push(int k, int l, int r) {
if (lazy[k] != ldef) {
dat[k] = (dic[r] - dic[l]) - dat[k];
if (r - l > 1) { setLazy(k * 2, lazy[k]); setLazy(k * 2 + 1, lazy[k]); }
lazy[k] = ldef;
}
}
};
int Q, A[101010], B[101010], C[101010], D[101010];
LazySegTree<ll, 1 << 18> st;
ll getall() {
return st.get(0, 1<<18);
}
void rev(int L, int R) {
st.update(L, R, 1);
}
void _main() {
cin >> Q;
rep(i, 0, Q) cin >> A[i] >> B[i] >> C[i] >> D[i];
rep(i, 0, Q) dic.push_back(A[i]), dic.push_back(C[i]);
sort(all(dic));
dic.erase(unique(all(dic)), dic.end());
rep(i, 0, Q) {
A[i] = lower_bound(all(dic), A[i]) - dic.begin();
C[i] = lower_bound(all(dic), C[i]) - dic.begin();
}
map<int, vector<pair<int, int>>> queries;
rep(i, 0, Q) {
queries[B[i]].push_back({ A[i], C[i] });
queries[D[i]].push_back({ A[i], C[i] });
}
ll prev = -inf;
ll ans = 0;
fore(q, queries) {
ll y = q.first;
ans += (y - prev) * getall();
fore(range, q.second) rev(range.first, range.second);
prev = y;
}
cout << ans << endl;
}