perogram

W - Intervals ~遅延セグ木(範囲加算・範囲Max)~

Quiz

https://atcoder.jp/contests/dp/tasks/dp_w

解説AC

https://atcoder.jp/contests/dp/submissions/8814646

感想

  • 論理はemtubasaさんの解説を参考
  • 遅延セグ木はふるやんさんのを借りてきた
    • いくつかパターンが書かれているから再利用しやすそう
    /*
    区間更新・区間和
    auto operation = [](ll a, ll b) { return a + b; };
    auto adapt_lazy = [](ll a, ll b) { return b; };
    auto merge_lazy = [](ll a, ll b) { return b; };
    auto multiply_lazy = [](ll a, int n) { return a * n; };
 
    区間加算・区間和
    auto operation = [](ll a, ll b) { return a + b; };
    auto adapt_lazy = [](ll a, ll b) { return a + b; };
    auto merge_lazy = [](ll a, ll b) { return a + b; };
    auto multiply_lazy = [](ll a, int n) { return a * n; };
 
    区間更新・区間最小
    auto operation = [](ll a, ll b) { return min(a, b); };
    auto adapt_lazy = [](ll a, ll b) { return b; };
    auto merge_lazy = [](ll a, ll b) { return b; };
    auto multiply_lazy = [](ll a, int n) { return a; };
 
    区間加算・区間最小
    auto operation = [](ll a, ll b) { return min(a, b); };
    auto adapt_lazy = [](ll a, ll b) { return a + b; };
    auto merge_lazy = [](ll a, ll b) { return a + b; };
    auto multiply_lazy = [](ll a, int n) { return a; };
    */
  • 範囲Maxセグ木を見つけてきても遅延セグ木じゃない(範囲加算できない)ものだったりして、探すにも時間がかかった
  • コンテスト中に探すのは避けたい
  • 今回のように1度ACしておくと安心して使える
  • 難易度は、水色の自分には少し早かったか