1日9時間寝たい

本当は10時間寝たいです

set

C: データ構造 - AtCoder Regular Contest 033 | AtCoder

解説スライドが丁寧です。

segtree

次の2つの操作が必要なのでsegtreeを使いましょう。

  • [1..200000]に含まれるある要素を1にしたり0にしたりする。
    • はじめは全ての要素を0で初期化しておく。
      • 集合の初期状態は空ということ。
    • 要素iが1のとき、iは集合に含まれている。
  • [l..r]の要素の和を求める。
    • 集合にl以上r以下の要素がいくつ含まれるかということ。

tlee

segtreeだとTLEになったのでbitreeを使いました。

bitree

和を求める操作は

  • [1..r]の要素の和を求める。

だけしか使わないのでbitreeで間に合います。*1

解答例

ARC 033-C データ構造

おわりに

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を足す操作でいいです。