ここに示されている問題があります。誰かがこの問題のアプローチを提案できますか? 社説を調べたところ、範囲ごとにツリーを作成し、それをノードとして扱うことになっているとありました.この概念とツリー変換のプロセスを理解できません.助けてくれてありがとう! 質問の詳細：
次の形式のシーケンスは、正しい括弧シーケンスと呼ばれます。
空のシーケンスは、正しい括弧シーケンスと見なされます。
(A) は、正しい括弧シーケンスと見なされます。
X と Y の両方が正しい括弧シーケンスである場合、XY は正しい括弧シーケンスと見なされます。
シーケンスが強い括弧シーケンスと呼ばれるのは、それが形式 (A) である場合に限られます。ここで、A は正しい括弧シーケンスです。
奇妙な合計を計算する必要があります: A の 2 つの部分配列ごとに [i1, j1] と [i2, j2] を取ります。部分配列は交差してはならず (つまり、i1 ≤ i2 および j1 ≤ i2)、強い括弧シーケンスでなければなりません。次に、サブ配列の最小長を合計に追加します。これは、強い括弧シーケンスでもあり、[i1, j1] と [i2, j2] の両方を含む (つまり、最小長のサブシーケンスが [i3, j3] の場合、[i3, j3] は強い括弧シーケンスであり、i3 ≤ i1 ≤ j1 ≤ j3 および i3 ≤ i2 ≤ j2 ≤ j3) です。
PS私は範囲のツリー変換の概念と、このコンテキストでLCAがどのように役立つかを理解できません.ありがとう.