Remove Extra One [Codeforces Round #450 C]

http://codeforces.com/contest/900/problem/C

N個の[1,N]からなる順列Pがある。
この順列から1つの数を抜いて、recordの要素の数を計算する。
recordの要素の数が最も多くなるのはどの数を抜いたときか。
複数答えがある場合は最も小さい数を答えよ。

※ recordの要素 : A[i]がrecordであるとは、全てのj

解法

http://codeforces.com/contest/900/submission/33117809

i番目の要素について考えてみる。

• 順列Pの区間[0,i)でP[i]よりも大きい数が…
  • 0個 : どの数を消してもA[i]はrecordになる
  • 1個 : 区間[0,i)の最大の数を消すとA[i]はrecordになる
  • 2個 : どう消してもrecordになれない

　　
これを踏まえてcnt配列を用意する。
cnt[i] := P[i]を消した時に増えるrecordの要素の数
これはi番目の要素全てについて、「順列Pの区間[0,i)でP[i]よりも大きい数が1個」の時に計算する。
区間[0,i)の最大の数の添字を取得するが、これはセグメントツリーを使えばいい。
この添字の要素を消せばrecordが1つ増えることになるのでcnt[この添字]をインクリメントする。
　
これをすれば配列cntが用意できそうだが、もし、P[i]が元々recordだった場合は、P[i]を消すと1つ減ることになる。
なので、P[i]がrecordかどうかを判定し、recordならcntを1つ減らす。
　
あとは、cnt[i]が最大となるように選ぶ。
最も小さい数を答える必要があるのに注意。

int N, P[101010];
BIT<int, 18> bit;
int cnt[101010];
SegTree<pair<int, int>, 1 << 18> st;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> P[i];
    rep(i, 0, N) st.update(i, { P[i], i });

    rep(i, 0, N) {
        if (bit.get(P[i] + 1, N + 2) == 1) {
            auto p = st.get(0, i);
            cnt[p.second]++;
        }
        bit.add(P[i], 1);
    }

    int mama = 0;
    rep(i, 0, N) {
        if (mama < P[i]) cnt[i]--;
        mama = max(mama, P[i]);
    }

    int ma = -1;
    rep(i, 0, N) ma = max(ma, cnt[i]);
    int ans = 101010;
    rep(i, 0, N) if (cnt[i] == ma) ans = min(ans, P[i]);
    cout << ans << endl;
}