https://atcoder.jp/contests/abc134/tasks/abc134_c?lang=en

给定长为N的序列，下标从1到N。 对于每个元素，输出序列里缺少这个序列之后的最大值。

解法：

N が数千以下 (言語によっては数万以下) なら、各問で A_i 以外の N − 1 個の要素すべてに対してループ を回して最大値を直接求めても実行制限時間の 2 秒に間に合います。しかし実際には N は最大で 20 万であ り、この方針では C++ でも間に合う望みはありません。計算時間を削減する方針を以下に二つ示します。

方針 1: 場合分け

ほとんどの場合、問いの答えは N 個すべての要素のうちの最大の値 A_max です。唯一の例外は問いで取り 除かれる値 Ai が A_max と等しい場合で、この場合の答えはすべての要素のうち 2 番目に大きい値 A_second (数列中に A_max が複数回現れる場合は A_second = A_max とします) です。問いの処理を始める前に A_max と A_second をあらかじめ求めておけば、各問を直ちに処理できます。なお、A_second を最も簡単な実装で求める 方法は、与えられた数列をコピーして言語の標準ライブラリでソートすることでしょう (やや「余計」な計算 をすることになりますが十分高速です)。

方針 2: 両端から攻める

j = 0, 1, . . . , N − 1 に対し、A₁, A₂, . . . , A_j のうちの最大の値を left_j とします (ただし left₀ = 0 としま す)。j ≥ 1 のとき left_j = max(left_j−1, A_j ) *1 であることに注意すると、これらの値は一周のループですべ て求められます。また、j = 2, . . . , N + 1 に対し、A_j , A_j+1, . . . , A_N のうちの最大の値を right_j とします (ただし right_N+1 = 0 とします)。j ≤ N のとき right_j = max(right_j+1, A_j ) であることに注意すると、こ れらの値も一周のループですべて求められます。問いの処理を始める前にこれらの値をあらかじめ求めておけ ば、各問 i の答えを max(left_i−1,right_i+1) として直ちに求められます。

import Data.List
main=do
    line<-getLine
    ctx<-getContents
    let p =[read x::Int | x<-lines ctx]
    let m=maxL p
    let r= length [1 | x<-p,(maxL p)==x]
    let s= if r==1 then maxL [x |x<-p ,x /= m] else m
    output p m s
maxL :: [Int]->Int
maxL [x] =x
maxL (x:xs) = max x (maxL xs)
output :: [Int]->Int->Int->IO()
output [] _ _ = return()
output (x:xs) m s
    | m/=s =do
         if x==m then putStrLn (show s) else putStrLn (show m )
         output xs m s
    | otherwise =do
         putStrLn (show m)
         output xs m s