問題概要

長さ $N$ の正の整数列 $A_{1}, A_{2}, \dots, A_{N}$ が与えられる。

$1, 2, \dots, N$ の順列 $p_{1}, p_{2}, \dots, p_{N}$ であって、

$A_{p_{1}} \le A_{p_{2}} \le \dots \le A_{p_{N}}$

を満たすものを考える。そのような順列の $p_{i} \gt p_{i+1}$ (ただし $p_{N} = 1$ である場合の $i = N-1$ の場合は除外) となっている箇所の個数の最小値を求めよ。

制約

$2 \le N \le 10^{5}$
$1 \le A_{i} \le 10^{5}$

考えたこと

本当に愚直にやると TLE になる。

ids[v] ← A[i] == v となる index i の集合

というデータをもつと上手に処理できる。僕の実装だと、 $M = \max_{i} A_{i}$ として、計算量は $O(N + M \log N)$ となる。

コード

#include <bits/stdc++.h>
using namespace std;
const int MAX = 110000;

int main() {
    vector<vector<int>> ids(MAX);

    // 入力
    int N;
    cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
        ids[A[i]].push_back(i);
    }

    int res = 0;
    int cur = 0;
    for (int v = 0; v < MAX; ++v) {
        if (ids[v].empty()) continue;
        int pl = lower_bound(ids[v].begin(), ids[v].end(), cur) - ids[v].begin();
        if (cur > ids[v][0]) cur = ids[v].back();
        else {
            ++res;
            cur = ids[v][pl-1];
        }
    }
    if (cur > 0) ++res;
    cout << res << endl;
}