はじめに
バグらせたくない
この記事ができたのはえびちゃんさんのおかげです．ありがとうございます．
ありがとうございます．
なんかまずかったら消します
rsk0315.hatenablog.com
本題
たまに出てきます．バグらせたくありません．どうしたらいいんだろう．ライブラリ化しましょう.
これがコードです．
バグっていたら教えてください．
閉区間をsetで管理しています．
だいたいどれもO(logn)で機能します．erase, insertで区間をたくさん消す時ヤバげに見えますが，結局今まで追加したものを消しているし，erase, insertで増える区間は高々1個なのでならしO(logn)とかいうやつになってるんじゃないですかね？ならしの計算量の概念がいまいちなので言葉をにごさせてください．
実際の使用例と解説
この問題を例に解説します．
codeforces.com
問題概要
最初1~nがonです．クエリl, r, kが飛んできます．k=1なら[l,r]をoffにします．k=2なら[l,r]をonにします．各クエリごとonの数を数えてください．
まぁなんというか，セグ木をしたくなります．が，nの制約がでかいです．ので，このデータ構造を脳を止めて貼ります．
insert, eraseをするときに区間の増減量を返すようにしているので無事に解けます．main内しか新しく書いていないとするとかなり楽な気がします．
このデータ構造のinsert部分だけ解説します．
はい．たいしたことしてないので15秒で書いた絵でゆるし帝
これも解けるよ！
covered_byを使って変更された区間をとってきて幅でchmaxすればいいです．
おわりに
コンテスト中に書くコードは少ない方が，いいよね？
こんな機能の追加したらどう？みたいなの募集しています．やろうと思えばいろんな機能を付けれると思っているので．
追記 (2020/11/10)
先日のABC182 E - Akariもこれで解けます．(これじゃなくても解けます)
僕はこれが割と楽だと感じています．
↓が提出です．
Submission #17994184 - AtCoder Beginner Contest 182
列ごと，行ごとに各マス，明かりが届くかを解きます
この時に，このデータ構造を使うと比較的記述量を少なく解くことができると考えています
- 壁ごとに仕切られた区間の集合stを用意します．最初，-1, wの位置に壁があるとして，st.insert(0,w-1)をしておきます
- st.erase(壁の位置)をすることで，区間を壁で仕切ります．
- [l, r] = st.covered_by(明かりの位置)をすることで，明かりが届く区間の範囲を取得できます
- [l,r]の位置にチェックをつけます．これはセグメント木でチェックしてもいいですし，それこそこのデータ構造を使ってもいいです．1個ずつチェックすると多分TLEします．
- 最終的にチェックがついているところには明かりが届きます
やっぱり区間をsetで管理するヤツ，そこそこ殴り力があると思っています．いや，もっと簡単にこの問題は解けるんですけど．
あと，こんなふうにデータ構造で殴れるよって言っておいて僕は本番この問題で2ペナはいています(おい)
