挙げ句、Dで方針をミスって無限にバグる桁DPに突入してタイムアップ。これもAIが秒で解いているので、桁DPのわけないと途中で気付いたのだけれど、ゴリ押しして時間が溶けた。結局バグ取りに3hかかった。
解答例をチラ見ても、「j桁目が1になる数の個数を数える」がどうやったらいいのか、桁DPしか思いつかない。熟読してやっと理解した。
というクソムーブで蓋を開けたら2完茶パフォ-63点。脳が腐ってる。

確かに、葉になるタイミングが悪いと、O(N)の葉を何度も親にマージする羽目になって、それはTLEする。
でも、色は全体で高々N個しかないわけだし、nとmが同時に大きいケースはそんなに多くない。なら、小さい方を回して大きい方にマージしたらうまくいくよね、と思って実装したらAC。但し、マージの方向が違うといろいろ計算が難しくて心が折れそうになった。

あと、コンテスト中にvscode落ちるのやめてほしい。markdownを検索した後にリンクを押すと必ず落ちる。