各箱に対して回転を行って \(h_i \leq w_i \leq d_i\) とした上で \(h_i \lt h_j, w_i \lt w_j, d_i \lt d_j\) を満たす \((i,j)\) が存在するかを判定、としても答えが変わらない(他の順番で高さ・幅・奥行きが上回る時、上記順番でも上回るため)のでそのようにします。また、大小関係にしか影響がないことから高さ・幅・奥行きごとに座標圧縮を行ってどの値も \(1\) 以上 \(N\) 以下にします。

まず、\(h_i\) が相異なる場合の解法を示します。各箱を \(h_i\) の昇順にソートして \(i\) の昇順になんらかの処理をすることにすると、「\(j\) 番目の箱に対する処理をしている時点で、今まで処理をした任意の箱 \(i\) に対して \(h_j \gt h_i\) 」が成り立ちます。これを生かし、以下のようにすると条件を満たす \((i,j)\) の存在判定が可能です。

• 一点更新と区間最小値取得が出来るサイズ \(N\) のセグメント木を用意する。
• \(i\) の昇順に次の処理を行う。
  • セグ木の添え字が \(w_i\) 未満の区間の最小値が \(d_j\) 未満ならば、Yes とする。
  • セグ木の添え字が \(w_i\) のところの値が \(d_i\) より大きいならば、\(d_i\) に置き換える。

本問では \(h_i\) が相異なるとは限らないため、このままだと \(h_i=h_j, w_i\lt w_j, d_i \lt d_j\) の場合に誤判定を起こしてしまいます。そこで、\((h_i,w_i,d_i)\) の組を \(h_i\) について昇順に、\(h_i\) が等しい場合は \(w_i\) について 降順 になるようにソートをすることで誤判定を防ぐことが出来、実質的に \(h_i\) が相異なる場合と同様に本問を解くことが出来ます。