Codeforces #464 Div2 E. Maximize!

少しずつConvex Hull Trickに慣れてきたかな。
http://codeforces.com/contest/939/problem/E

問題

初期状態で空集合のSがある。
以下のクエリに適宜答えよ。

• Sに整数xを加える。xは過去のクエリで最大である。
• Sの部分集合S'のうち、max(S')-mean(S')の最大値を求める。

解法

後者のクエリに関しては、S'同じ要素数ならmaxだけ大きいものを選び、それ以外は小さいものを選ぶとよい。
S'がN要素の場合、Sから小さい順に(N-1)選んだ和がP、最大値をQとすると、max(S')-mean(S') = Q - (P+Q)/N = Q*(N-1)/N - P/N
これはQに対する1次式である。

よって、Sに要素が増えるたびに1次式x*(N-1)/N - P/Nが増えると考え、Convex Hull Trickでxに対する最大値を求められるようにしよう。

template<typename V> struct ConvexHull {
	deque<pair<V,V>> Q;
	int cmptype=0; // 0-max 1-min
	V calc(pair<V,V> p, V x) {
		return p.first*x+p.second;
	}
	int dodo(pair<V,V> A,pair<V,V> B, pair<V,V> C) { // max or min
		return cmptype^((B.second-C.second)*(B.first-A.first)<=(A.second-B.second)*(C.first-B.first));
	}
	void add(V a, V b) { // add ax+b
		Q.push_back({a,b});
		int v;
		while((v=Q.size())>=3 && dodo(Q[v-3],Q[v-2],Q[v-1]))
			Q[v-2]=Q[v-1], Q.pop_back();
	}
	void add(vector<pair<V,V>> v) {
		sort(v.begin(),v.end());
		if(cmptype==1) reverse(v.begin(),v.end());
		for(auto r=v.begin();r!=v.end();r++) add(r->first,r->second);
	}
	
	
	V query(V x) {
		int L=-1,R=Q.size()-1;
		while(R-L>1) {
			int M=(L+R)/2;
			(cmptype^((calc(Q[M],x)<=calc(Q[M+1],x)))?L:R)=M;
		}
		return calc(Q[R],x);
	}
};
ConvexHull<double> ch;

int N;
ll S;
int Q,T,X;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d",&Q);
	while(Q--) {
		scanf("%d",&T);
		if(T==1) {
			if(N) {
				ch.add(N/(N+1.0),-S*1.0/(N+1));
			}
			scanf("%d",&X);
			N++;
			S+=X;
		}
		else {
			if(N==1) _P("0\n");
			else _P("%.12lf\n",ch.query(X));
		}
	}
	
}

まとめ

xが段々大きくなるって条件を外すと難しいのかな？