Codeforces Round #332 (Div. 2) C. Day at the Beach

出る気まんまんだった Codeforces Round #332 (Div. 2) は寝坊。

問題

codeforces.com

解法

ある区間 [l, r] でソートしてやるだけで全体をちゃんとソートしたことになるためには, [0, r] に含まれる数が, 全体で見た時に [0, r] 番目の数のみで構成されていれば良いです。

よって, 0 番目から i 番目まで順番に見ていった時に, 今まで見た数が [0, i] 番目の数になっているかを確かめれば良いです。これは binary indexed tree を使えば良さ気ですね。

// 0-based Binary Indexed Tree
// 数え上げ用
constexpr int mod = 1e9+7;
template<typename T> struct BIT {
    int max;
    vector<T> bit;
    BIT(int max) : max(max) {bit.resize(max+1);}
    // [0, i)
    T sum(int i) {
        T s = 0;
        while (i > 0) {
            (s += bit[i]) %= mod;
            i ^= i&-i;
        }
        return s;
    }
    // 0-basedな座標iに値xを追加する
    void add(int i, T x) {
        ++i;
        while (i <= max) {
            (bit[i] += x) %= mod;
            i += i&-i;
        }
    }
    // [a, b)
    T sum(int a, int b) {
        return sum(b)-sum(a);
    }
    // sum(0, i) >= wとなる最小のiを求める 存在しなければmaxを返す
    int lb(T w) {
        if (w <= 0) return 0;
        int k = 1;
        while (k <= max) k <<= 1;
        int i = 0;
        for (; k > 0; k >>= 1) if (i+k <= max && bit[i+k] < w) {
            w -= bit[i+k];
            i += k;
        }
        return i+1;
    }
};

const int MAXN = 100010;
int h[MAXN];
pii p[MAXN];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> h[i];
        p[i].first = h[i];
        p[i].second = i;
    }
    sort(p, p+n);
    for (int i = 0; i < n; i++) {
        h[p[i].second] = i;
    }
    BIT<int> bit(n);
    int ans = 0;
    for (int i = 0; i < n; i++) {
        bit.add(h[i], 1);
        if (bit.sum(i+1) == i+1) ans++;
    }
    cout << ans << endl;
    return 0;
}