yukicoder - No.878 Range High-Element Query
解説
前処理として、各要素の左にあるものかつその要素より大きいもので、最も近いものをメモしておきましょう。
これはstd::setなどで簡単にできます。
次にクエリを先に読んでが小さいものから見ていきます。
現状条件をみたしてるものをBITにいれていけばよく、が終わるたびに、最初にメモしたのが
だったものをBITに入れていきましょう。
計算量はです。
前処理として、各要素の左にあるものかつその要素より大きいもので、最も近いものをメモしておきましょう。
これはstd::setなどで簡単にできます。
次にクエリを先に読んでが小さいものから見ていきます。
現状条件をみたしてるものをBITにいれていけばよく、が終わるたびに、最初にメモしたのが
だったものをBITに入れていきましょう。
計算量はです。