Codeforces #174 Div1. A. Cows and Sequence

さてここからが本番。
http://codeforces.com/contest/283/problem/A

問題

初期値として0が一つ入った数列が与えられる。
ここに以下のクエリを順に処理した場合に、数列の平均値を答える。

1. 数pとqが与えられるので、数列の先頭p個にqを加算する。
2. 数Kが与えられるので、数列の末尾に追加する。
3. 数列の末尾の要素を削除する。

解法

数列長さLL、数列の合計T、クエリ2で与えられるi番目の配列要素L[i]、クエリ1で与えられるi番目までの要素にそれぞれ加算されるA[i]をクエリごとに管理して行けばよい。
各クエリ後にT/LLが答えとなる。
クエリ3によりLL個の要素に加算すべきA[LL]を(LL-1)個分に加算するようA[LL]を1個分減らすのがコツ。

1. クエリ1の場合、A[p]にqを足し、Tにp*qを足す。
2. クエリ2の場合、L[LL]およびTにKを足し、LLをインクリメントする。
3. クエリ3の場合、TからL[LL]とA[LL]を減らし、A[LL-1]にA[LL]を足し、LLをデクリメントする。

ll L[200002];
ll A[200002];
ll T;

void solve() {
	int f,r,i,j,k,l, x,y,ma,num,nt;
	char s[100];
	
	int LL=1;
	int N=GETi();
	FOR(i,N) {
		j=GETi();
		if(j==1) {
			x=GETi();
			y=GETi();
			A[x]+=y;
			T+=x*y;
		}
		else if(j==2) {
			L[++LL]=GETi();
			T+=L[LL];
		}
		else if(j==3) {
			T-=L[LL]+A[LL];
			A[LL-1]+=A[LL];
			A[LL]=0;
			LL--;
		}
		
		_P("%.9lf\n",T/(double)LL);
	}
	
	return;
}

まとめ

多数のクエリを処理する問題、CFでは多いな…。