AtCoder ARC #008 : D - タコヤキオイシクナール

Cでタイムロスしすぎて、本番中はDはSmallを素直にシミュレートするのが精いっぱい。
他の方の回答を参考にしつつDも練習で実装。
http://arc008.contest.atcoder.jp/tasks/arc008_4

M=100000もあるので、O(M^2)では間に合わない。
途中のマシンを入れ替えた場合に、O(M)より短い時間でおいしさを計算できないといけない。

そこでセグメント木が使えるようだ。
２つの連続する機械l,rのパラメータがとすると、おいしさrのたこやきに２台分の機械を連続して適用したおいしさはとなる。
なので、２台分を統合したパラメータは、となる。
２台分のマシンを１台分にマージできたので、これを再帰的に行うと17回マージすれば2^17>100000個分のマシンのパラメータを１台分にマージできるので、これで答えが出せる。
よって計算量はO(M log M)かな。

s64 N;
int ID[100001];
double A[100001],B[100001];
pair<s64,int> ps[100001];
const int SEG=1<<18;
int NSEG,M;
double SA[SEG],SB[SEG];

double update(int id, double AA, double BB) {
	int s=0, w = NSEG/2;
	SA[id]=AA;
	SB[id]=BB;
	while(w>1) {
		int l = s+(id/2)*2;
		int n = s+w+id/2;
		SA[n]=SA[l]*SA[l+1];
		SB[n]=SA[l+1]*SB[l]+SB[l+1];
		id /= 2;
		s += w;
		w /=2;
	}
	
	return SA[NSEG-2]+SB[NSEG-2];
}

void solve() {
	int x,y,i,j,p,rr,TM;
	s64 kk;
	double mind,maxd,fd;
	
	scanf("%lld%d",&N,&M);
	FOR(i,M){
		scanf("%lld%lf%lf",&kk,&A[i],&B[i]);
		ps[i].first=kk;
		ps[i].second=i;
	}
	
	sort(ps,ps+M);
	TM=0;
	FOR(i,M){
		if(i!=0 && ps[i].first!=ps[i-1].first) TM++;
		ID[ps[i].second]=TM;
	}
	TM++;
	
	
	NSEG=SEG;
	while(NSEG>=TM*4) NSEG>>=1;
	FOR(i,SEG){ SA[i]=1; SB[i]=0;}
	
	mind=maxd=1;
	FOR(i,M) {
		fd = update(ID[i],A[i],B[i]);
		mind=min(mind,fd);
		maxd=max(maxd,fd);
	}
	
	_P("%.8lf\n%.8lf\n",mind,maxd);
}

まとめ

ラインの途中のマシンを差し替えた際に全体のパラメータを高速に更新するのにセグメント木が使えそう。
データ構造の勉強になったね。