Educational Codeforces Round 64 - E. Special Segments of Permutation

問題リンク

計算量解析が本質の問題だね

解法

まず a _ {i}がどこまでの範囲で最大値になるかを求めよう！

これはstackを使うことで O(n)でできることは有名である。

そうすると a _ {i}より左のパートと a _ {i}より右のパートから1つずつとってきて和が a _ {i}になるような数を調べたらいい。

一見 O(n ^ 2)に見えるが、実は左のパートと右のパートの小さいほうをみることで O(n \log n)になる。

実際になめる要素が各区間の半分以下になっていくからだ！

このことから、各要素はせいぜい O(\log n)回しかなめられず、よって全体の計算量としては O(n \log n)になる

提出コード

codeforces.com

まとめ

マージテクとかと似たような感じだね