Sorting the Coins [Codeforces Round #441 B]

http://codeforces.com/contest/875/problem/B

N枚のコインがあり、最初は全部表である。
以下の手続きを1セットとして行う。
1. コインを右から左に順番に処理する
2. i番目が裏で(i+1)番目が表なら、i番目を表に(i+1)番目を裏にする

p[1],p[2],...,p[N]が与えられる。
これはi回目にp[i]番目を裏にした状態にすることを示す。
a[i] = p[1]～p[i]番目を裏にした状態から初めて手続きを何回やれば、裏返しにできなくなるか
（a[0]は全て表スタートを示し、裏返しにできなくなるかチェックする手続きも1回としてカウントする）

N≦3*10^5

解法

http://codeforces.com/contest/875/submission/31396064

証明してない多分こうだろうという解法。
答えは「右端とつながっていない裏の枚数+1」である。
右端とどれほどつながっているかは、尺取法のような感じで更新していけば良い。
あとは、何個裏があるかはBIT(下のコードではセグ木使っているけど)を使えばいい。

int N, A[301010];
int ans[301010], B[301010];
SegTree<int, 1 << 20> bit;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];
    
    ans[0] = 1;
    int L = N - 1;
    rep(i, 0, N) {
        int a = A[i] - 1;

        B[a] = 1;
        bit.add(a, 1);

        while (0 <= L && B[L]) L--;

        if (L < 0) {
            ans[i + 1] = 1;
        }
        else {
            int c = bit.get(0, L);
            ans[i + 1] = c + 1;
        }
        
    }

    rep(i, 0, N + 1) {
        if (i) printf(" ");
        printf("%d", ans[i]);
    } printf("\n");
}