AtCoder ABC #292 : Ex - Rating Estimator

Exの割に、割とすんなり解法が思いつけた。
https://atcoder.jp/contests/abc292/tasks/abc292_h

問題

N個のコンテストで、それぞれ得られるパフォーマンスの履歴が与えられる。
n個目までコンテストに出たとき、レートはその平均値となる。
ただし、途中でレートがB以上になると、以降コンテストに参加してもレートは変化しなくなる。

1つのコンテストの履歴を変更するクエリが与えられるので、N個のコンテストに参加した後のレートを求めよ。

解法

N個のコンテストのパフォーマンスを順に並べた数列において、Prefixの平均がB以上になる最短の長さをnとする。
(もし平均がB以上になることがないならn=Nとする)
そうすると解は先頭n要素の平均値が解となる。

各パフォーマンスをあらかじめB引いた状態を考えると、prefix sumが0以上になる(1以上で)最短の長さnを求められれば良い。
これはSegTree上で二分探索するなどで求めることができる。

int N,Q;
ll B;
ll A[505050];

template<class V,int NV> class SegTree_1 {
public:
	vector<V> sum,ma;
	static V const def=0;
	V comp(V l,V r){ return max(l,r);};
	
	SegTree_1(){
		sum=vector<V>(NV*2,def);
		ma=vector<V>(NV*2,def);
		ma[NV]=-(1LL<<60);
	};
	pair<V,V> getval(int x,int y,int l=0,int r=NV,int k=1) { // x<=i<y
		if(r<=x || y<=l) return {0LL,-1LL<<60};
		if(x<=l && r<=y) return {sum[k],ma[k]};
		auto a=getval(x,y,l,(l+r)/2,k*2);
		auto b=getval(x,y,(l+r)/2,r,k*2+1);
		return {a.first+b.first,max(a.second,a.first+b.second)};
	}
	
	void update(int entry, V v) {
		entry += NV;
		sum[entry]=v;
		ma[entry]=v;
		while(entry>1) {
			entry>>=1;
			sum[entry]=sum[entry*2]+sum[entry*2+1];
			ma[entry]=max(ma[entry*2],sum[entry*2]+ma[entry*2+1]);
		}
	}
};
SegTree_1<ll,1<<20> st;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>B>>Q;
	for(i=1;i<=N;i++) {
		cin>>A[i];
		A[i]-=B;
		st.update(i,A[i]);
	}
	
	FOR(i,Q) {
		cin>>x>>y;
		A[x]=y-B;
		st.update(x,y-B);
		if(st.ma[1]>=0) {
			int R=N;
			for(j=20;j>=0;j--) if(R-(1<<j)>=1&&st.getval(0,R-(1<<j)+1).second>=0) R-=(1<<j);
			_P("%.12lf\n",1.0*st.getval(0,R+1).first/R+B);
			
		}
		else {
			_P("%.12lf\n",1.0*st.sum[1]/N+B);
		}
	}
	
}

まとめ

「数列の平均がX以上」というのは、「各要素あらかじめX引いたうえで平均が0以上」と言い換えると、長さを考慮しなくてよくなるという定番テク。