Codeforces #441 Div1 B. Sorting the Coins

これもまだ簡単。
http://codeforces.com/contest/875/problem/B

問題

N個のコインが1列に並んでいる。
N個のコインを１個ずつ抜き出し、その順番が与えられる。
抜き出すごとに、以下のクエリに答えよ。

コイン列を１回なぞることを考える。
もしi列目が空白で(i+1)列目にコインが残っているなら、コインを前にずらす。
ということをiを昇順に行う。

上記処理を、これ以上コイン列が動かなくなるまで繰り返す場合、何回コイン列をなぞる必要があるか。

解法

各クエリの回答は、残された最も末尾のコインに対し、(手前にある空白の数+1)である。
空白の数はbitで、残された末尾のコインの位置はsetで管理すればよい。

int N;
int P[302020];

template<class V, int ME> class BIT {
public:
	V bit[1<<ME];
	V operator()(int e) {if(e<0) return 0;V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;}
	void add(int e,V v) { e++; while(e<=1<<ME) bit[e-1]+=v,e+=e&-e;}
};
BIT<int,20> bt;


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	_P("1");
	set<int> S;
	FOR(i,N) {
		S.insert(i+1);
		bt.add(i+1,1);
	}
	FOR(i,N) {
		cin>>x;
		bt.add(x,-1);
		S.erase(x);
		
		if(S.empty()) {
			_P(" 1\n");
		}
		else {
			x=*S.rbegin();
			
			_P(" %d",1+(x-1)-bt(x-1));
		}
	}
}

まとめ

ここら辺までは通常より簡単だね。