本質的な解法は公式解説と同じです。

この問題は俗に双対セグ木と呼ばれるデータ構造の考え方を用いて解くことができます。

双対セグ木とは

• 区間更新クエリ（区間加算など）
• 1点取得クエリ

の2種類のクエリを高速に処理するためのデータ構造であり、直感的に言えば遅延セグ木の作用素だけを持ったものです。

この問題では区間更新クエリが可換であるため、(遅延セグ木ではなく) starry sky tree の作用素だけを持ったものだと思うことができます（こちらのみを指して双対セグ木と呼ぶ流派も存在するようです）。このケースでは、区間更新クエリを処理する場合に、(starry sky treeと同様に)作用素を子ノードに渡して更新する必要がなくなることに注意してください。

本題に戻ります。まず、取り消しクエリがない問題は、作用 \(\mathrm{chmax}(x,\cdot)\) を整数 \(x\) で表すことにより次のように解けます。

• 区間chmax
  • 更新すべき区間に対応するセグ木のノードの作用素を更新
• 1点取得
  • 取得する対象のとなるセグ木の葉ノードから根まで遡って作用素を作用させる

取り消しクエリを処理するためには、それまでの作用素を全て記録しておけば良さそうです。実際、各ノードでいままでの作用素を全て ordered_multiset で管理することにすれば、削除と最大値の取得がともに高速にできるため、この問題を解くことができます。

実装例(C++)