観察: クエリ 1 の持つ性質は？

クエリ 2, クエリ 3 だけならば典型的な遅延評価セグメント木(以下 lazyseg) に関する問題です。問題はクエリ 1 で、これがどのような性質を持つのか見ていきましょう。

1. 通常の lazyseg に載らない

lazyseg に載る代数的な構造は実はかなり限られています。(lazyseg に載る条件は ACL のリファレンス に載っています。)クエリ 1 のような整数除算はこの条件を満たしていないので、lazyseg にそのまま載せることはできません。

2. クエリを適用するごとに a_i の値が半分以下になる

クエリ 1 を適用するごとに、区間に含まれている要素は\(a_i\) から \(\lfloor a_i / x\rfloor \leq a_i / 2\) へ変化するので、要素の値は半分以下になります。そして、一旦 \(0\) になったらクエリ \(2\) (更新クエリ) が適用されるまでクエリ 1 の影響を受けません。これが計算量を削減する 1 つのポイントになります。

以上のポイントに注目して解法を考えていきましょう。 ここでは 2 種類の解法を紹介します。

解法 1 : 区間を set で管理

1 つ目の解法はオーソドックスな解法で、前回の Ex 問題にも登場している区間を set で管理するテクニックを利用してみましょう。
「値が同じであり、かつ \(1\) 以上である区間」を std::set で管理することを考えます。また、別途 range assign と range sum ができる lazyseg を用意して、そちらでも \(A\) の要素を管理します。
クエリ 2 は std::set に適宜区間を挿入して lazyseg に range assign を行えば高速に処理できます。クエリ 3 も lazyseg を利用すればよいです。また、\(A\) の初期状態をデータ構造に反映させる部分も、クエリ \(2\) が \(N\) 回投げられたと見なせば高速に処理できます。
問題はクエリ 1 です。まず、 \([L,R]\) に含まれる非 \(0\) な区間を std::set を走査することで列挙します。各区間は値が同じなので、整数除算を適用した後の値はただちに求まり、 lazyseg の値も \(\mathrm{O}(\log N)\) で更新できます。また、値が \(0\) になった場合は std::set から区間を取り除きます。

計算量を考えます。1 つの区間を std::set に挿入する回数は高々 \(\lceil \log \max(A) \rceil + 1\) 回です。また、新たな区間が挿入される回数は \(N + \mathrm{O}(Q)\) 回です。よって計算量は \(\mathrm{O}( (N + Q) \log N \log \max(A))\) になります。

実装例

以下は発展的な内容ですが、データ構造の知識がある人や興味がある人向けの別解として Segment Tree Beats! を紹介します。

解法 2 : Segment Tree Beats!

Segment Tree Beats! (以下 Beats) は 2016 年頃に中国の情報オリンピック界隈で開発されたデータ構造です。

• Codeforcesの記事(英語) ：作者の吉さんによる解説。中国では「吉老师线段树」のような呼び名も用いられているようです。

Beats は lazyseg を拡張したデータ構造と言えるので、ここでは非再帰の lazyseg である ACL の lazy_segtree の実装 を元に説明していきましょう。

lazyseg の区間更新 (ACL の apply 関数) は次のように作用素を作用させています。

1. 根から葉の方向に向けて、遅延評価用の値を伝搬していく。(ACL の push 関数)
2. \(\mathrm{O}(\log N)\) 個の区間に対して、作用素を作用させて遅延評価用の値を更新する。(ACL の all_apply 関数)
3. 葉から根の方向に向けて、作用素を作用させた後の値をもとに値を更新していく。(ACL の update 関数)

このような操作によって区間更新・区間和の取得ができるのは、モノイド \(S\) および作用素 \(F\) が良い性質を持っているからです。
では、もしも作用素が「ときどき失敗する」場合はどうなるでしょうか。つまり、作用素が現在のモノイドの持つ値によって作用できたり作用できなかったりする状況を考えてみます。(作用素がこのような性質を持つ場合に lazyseg にそのままモノイドと作用素を持たせると、もちろん 2. で作用に失敗してめちゃくちゃなことになります。)
とりあえず、作用素が長さ 1 の区間に対しては必ず作用できることを仮定しましょう。すると、「作用に失敗してしまう場合は、かわりに子への作用を試みる」という操作を再帰的に繰り返せば、正しく動作するアルゴリズムを構成することができます。(どれだけ作用できない状況が続いても最後には長さ 1 の区間に辿り着くため。)すなわち次のようなアルゴリズムです。

1. 根から葉の方向に向けて、遅延評価用の値を伝搬していく。
2. \(\mathrm{O}(\log N)\) 個の区間に対して、作用素を作用させるのを試みる。
   • 作用させられる場合は、通常の lazyseg と同様に作用させて遅延評価用の値を更新する。
   • そうでない場合は、子の要素への作用を試みる。これを作用させられるまで再帰的に繰り返す。
3. 葉から根の方向に向けて、作用素を作用させた後の値をもとに値を更新していく。

上記のアルゴリズムならば作用に失敗することはありませんが、最悪ケースで \(\mathrm{O}(N)\) かかってしまうという問題があってこちらをどうにかしなければいけません。
lazyseg で訪問するノードを ordinary nodes, Beats で新たに訪問するノードを extra nodes と定義します。ordinary nodes は lazyseg が訪問するノードでクエリあたり \(\mathrm{O}(\log N)\) で済むので extra nodes の個数のみが重要になります。ここでモノイドおよび作用素をうまく設計することで、問題全体で訪れる extra nodes の個数が \(\mathrm{o}(QN)\) になるようにできれば、更新クエリが償却 \(\mathrm{o}(N)\) になって計算量を落とすことができます。

• 発想自体は簡単ですが、この部分を問題に応じて ad-hoc に設計・計算量解析する必要があるのが Beats の難しいところです。

この問題での解法は次のようになります。

ABC256H で Beats に載せるデータ

各区間 \([L,R]\) に対して、次の \(4\) つを載せます。

• 区間に含まれる要素の和 \(\sum_{i=L}^R a_i\)
• 区間の左端の要素 \(a_L\)
• 区間の長さ \(R - L + 1\)
• 区間に含まれる値 \(a_i\) がすべて等しいかを持たせたフラグ

このとき、クエリ 1 に由来する作用素が作用できる条件は「フラグが true かどうか」になります。詳しくは実装例の該当部分を以下に抜き出すのでそちらを参考にしてください。

using T = long long;
using U = pair<int, int>;
struct Node {
  T sm, val;
  int size;
  bool same;
  Node(T n = 0) : sm(n), val(n), size(1), same(true) {}

  void query2(T x) { sm = x * size, val = x, same = true; }
  void push(Node& l, Node& r) {
    if (same) l.query2(val), r.query2(val);
  }
  void update(Node& l, Node& r) {
    sm = l.sm + r.sm;
    val = l.val;
    size = l.size + r.size;
    same = l.same and r.same and l.val == r.val;
  }
  bool apply(U p) {
    if (p.first == 1) {
      return same ? (query2(val / p.second), true) : false;
    } else {
      return query2(p.second), true;
    }
  }
};

計算量解析

extra node 以外の部分は \(\mathrm{O}(N + Q \log N)\) で計算できるので考えなくて良いです。訪問する extra node の個数をうまく評価します。

区間 \([l, r]\) に対して \(f(l,r)\) を次のように定義します。

\[ f(l, r) = \begin{cases} 0 & \text{if } a_l = a_{l+1} = \dots = a_r \\ -\log_2 \max(a_l, a_{l+1}, \dots, a_{r}) - 1 & \text{otherwise} \end{cases} \]

そして、ポテンシャル \(\phi\) をすべてのノードにおける \(f\) の和として定義します。\(\phi\) の変化に注目することで、extra node に訪れる回数が \(2(N + Q \lceil \log N \rceil) \lceil \log \max(A) + 1 \rceil\) 回以下なのを示します。

\(\phi_i :=\) (\(i\) 番目のクエリが終了した時点でのポテンシャル) とおきます。\(\phi_0 \geq -2N \lceil \log \max(A) + 1 \rceil\) です。また、クエリ \(2\) が呼ばれるごとに 新たに \(f(l, r) \neq 0\) となるノードは ACL の update 関数が呼ばれる箇所の個数に等しいので、\(i\) がクエリ \(2\) のとき \(\phi_i - \phi_{i-1} \geq -2 \lceil \log N \rceil \lceil \log \max(A) + 1 \rceil\) です。よってクエリ全体でのポテンシャルの減少量は \(-2(N + Q \lceil \log N \rceil) \lceil \log \max(A) + 1 \rceil\) で抑えられます。

また、クエリ \(1\) で \(1\) 個の extra nodes に訪れるごとに、そのノードの最大値が \(1/2\) 以下になるのでポテンシャルが \(1\) 以上増えます。また、定義よりポテンシャルは常に \(0\) 以下です。よって、extra nodes に訪れる回数は \(2(N + Q \lceil \log N \rceil) \lceil \log \max(A) + 1 \rceil\) 回以下であることが確認できました。

以上より Beats を利用した解法の計算量は \(\mathrm{O}( (N+Q \log N) \log \max(A))\) であることが確認できました。

実装に関しては lazyseg が書ける人ならば難しい所はないと思います。また、hitonanode さんが ACL の lazyseg を少し改造して Beats にする方法を書いていて参考になると思います。hitonanode さんの記事

実装例