set
C: データ構造 - AtCoder Regular Contest 033 | AtCoder
解説スライドが丁寧です。
segtree
次の2つの操作が必要なのでsegtreeを使いましょう。
- [1..200000]に含まれるある要素を1にしたり0にしたりする。
- はじめは全ての要素を0で初期化しておく。
- 集合の初期状態は空ということ。
- 要素iが1のとき、iは集合に含まれている。
- はじめは全ての要素を0で初期化しておく。
- [l..r]の要素の和を求める。
- 集合にl以上r以下の要素がいくつ含まれるかということ。
tlee
segtreeだとTLEになったのでbitreeを使いました。
bitree
和を求める操作は
- [1..r]の要素の和を求める。
だけしか使わないのでbitreeで間に合います。*1
解答例
おわりに
1997ms(TimeLimit:2000ms)で通って嬉しかった。
これ解きたいですね。(解ける難易度なのだろうか)
http://codeforces.com/blog/entry/22616
参考
https://www.slideshare.net/iwiwi/ss-3578491
http://hos.ac/slides/20140319_bit.pdf(PDF)
*1:1にしたり0にしたりする操作は±1を足す操作でいいです。