部分的に順序付けされたセットで指定されたより大きい要素を見つけよう

Question

私は、タイプの要素をTと設定しています。タイプTの要素には、部分注文<=があります。 Sのすべての要素は注文されていません。 次に、次のクエリを実行する方法が必要です。eタイプがTの、e'がSで、e <= e'のようになります。

このようなクエリを効率的に実行できるデータ構造がありますか（リニアスキャンなしでS）？

重要な注記：Tは完全な格子です。

Answer 1

リストを前処理して、それらの数値より大きい他の要素を持たない要素のサブセットを見つけることができます（すべての数値をダグとして表現したと仮定し、親を持たない要素をすべて見つける必要があります）。そのサブセットを取得したら、このサブセットのリニアスキャンだけです。私はあなたがこれよりもうまくいくとは思わない。

また、このサブセットを、サブセット内のこれらの要素のそれぞれの要素の数でソートすることもできます（降順）。要素を順番にスキャンします。