ジョギングをした。1.5km。

なんか肺がすごく苦しくなった。呼吸のための筋肉が衰えている気がする。

---

今日解いた競プロの問題。

Donutsプロコン2015-C: まず見た目でDPっぽいなということが分かる。dp[h]:=(高さhの人越しに見える人の数) と置くとよい。愚直にやると$O(N\max H)$、座圧しても$O(N^2)$なので高速化しようということになる。

for(int i = 0; i < n; i++){
  cout << dp[0] << endl;
  int tmp = dp[h[i]] + 1;
  for(int j = 0; j <= h[i]; j++) {
    dp[j] = tmp;
  }
} 

区間代入なので双対セグ木を貼るだけ。恐ろしいことに気付いたのだが、実は今まで使っていた双対セグ木が非可換演算に対応していなかった。精進中に気付けて良かった。

双対セグ木は更新する場合木の根側から伝播させ、取得する場合は木の葉側から順に計算する。非可換演算に対応させる場合を考えると、後に行った更新ほど木の根側になるよう順序が保たれなければならない。もしもナイーブに

• 現在のノードの担当範囲⊂更新範囲 ならば更新
• 現在のノードの担当範囲∩更新範囲＝∅ ならば無視
• どちらでもなければ下の2ノードに丸投げ

という実装をすると、順番がごちゃごちゃになってしまう。これでも可換であれば問題は起きない。順序は崩れるとしても、各点について行われた更新操作はその点を担当するノードのどれかには記録されるからだ。非可換演算に対応する場合、どちらでもない場合に単に下のノードに丸投げするのではなく、現在のノードに記録された演算を下に下ろす操作を付け加える必要がある。

---

スプラトゥーンをした。

ナワバリ 5勝1敗

ガチマ 3勝0敗