問題タブ [range-query]

かっこの文字列が与えられた場合、2 種類の操作を行う必要があります。

1. 反転 - i 番目の括弧を反対の括弧に変更します (left->right 、 right->left)
2. チェック - 文字列がバランスの取れた括弧式であるかどうか

文字列の長さは最大 30000 です。

実行する操作の数は最大 100000 です。

この種の問題を解決するには、どのようなデータ構造を使用する必要がありますか?

セグメント ツリーは適切なデータ構造ですか?

はいの場合、どのように使用する必要がありますか？

例

文字列 = ()((

操作数=4

1. フリップ 4 {新しい文字列は ()()}
2. check {文字列はバランスが取れています}
3. フリップ 2{新しい文字列は ((()} になります)
4. check{文字列のバランスが取れていません}

ここに示されている問題があります。誰かがこの問題のアプローチを提案できますか? 社説を調べたところ、範囲ごとにツリーを作成し、それをノードとして扱うことになっているとありました.この概念とツリー変換のプロセスを理解できません.助けてくれてありがとう! 質問の詳細：

次の形式のシーケンスは、正しい括弧シーケンスと呼ばれます。

• 空のシーケンスは、正しい括弧シーケンスと見なされます。

• (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がどのように役立つかを理解できません.ありがとう.

私はelasticsearchを介してインデックスを作成したドキュメントの次のセクションを取得しようとしています:

現在ローカルホストでクエリをテストしているだけなので、CURLで使用しているクエリは次のとおりです。

マッピング

ただし、上記のクエリは、少なくとも上記のドキュメントを返す必要がありますが、成功したヒットを返しません。

エラスティック サーチが転置インデックスを使用している場合、エラスティック サーチが範囲クエリとフレーズ クエリをどのようにサポートできるかを知りたいです。注：逆インデックスがそれらをサポートしていることを見ましたが、内部でどのように行うかは明確ではありません。

データをelasticsearchデータベースに保存していて、数値の範囲でフィルタリングしてクエリを実行しようとしています。

これは、データベース内のドキュメントの構造を最小化したものです。

ここで、「b」のいずれかのサブフィールドに 2 ～ 4 の範囲の数字が少なくとも 1 つ含まれるすべてのドキュメントをクエリで返すようにします。ここで重要なことは、「」のすべてのサブフィールドの名前がわからないことです。 b」。

私が思いついたクエリは次のとおりです。

クエリはエラーを発生させませんが、結果も返しません。そのようなタスクにどの種類の検索クエリが最も適しているかさえ、私にはよくわかりません。不明なフィールド名と範囲を結合できる唯一のクエリ文字列が見つかったため、クエリ文字列のみを使用しました。