Codeforces #370 Div2 E. Memory and Casinos

SegTreeまで思いついても、その次が難しそう。
http://codeforces.com/contest/712/problem/E

問題

N個のカジノ店が１列に並んでいる。
i番の店では、確率P[i]で勝利する。
勝利すると次の番号の店に、負けると１つ前の番号の店に移動する。

以下のクエリQ個の答えよ。

• i番の店の勝利確率を入力値に置き換える。
• 店の区間[x,y]が与えられる。x番の店から初めて、x番の店で負けるかy番の店で勝つかいずれかまでカジノで勝ち負けを繰り返し、後者で終わる確率を答えよ。

解法

区間[x,y]に対し、以下を定義する。
L(x,y) := x番の店で始めた場合、x番の店で負けるかy番の店で勝つかいずれかまでカジノで勝ち負けを繰り返したとき後者で終わる確率
R(x,y) := y番の店で始めた場合、同上

２つの区間[a,b][b+1,c]に対しL(a,b)=L1, R(a,b)=R1, L(b+1,c)=L2 ,R(b+1,c)=Rとしたとき、これらでL(a,c)、R(a,c)を求めることを考える。
これが出来れば、あとはSegTreeの要領で、クエリ区間(x,y)のL(x,y)を答えればそれが解になることがわかる。

なお、L(a,c), R(a,c)は以下のように表せる。

• 
• 

int N,Q;
double P[101010];

const int NV=1<<18;
pair<double,double> M[NV*2];

pair<double,double> merge(pair<double,double> p1,pair<double,double> p2) {
	pair<double,double> p;
	p.first = (p1.first*p2.first)/(1+p1.second*(p2.first-1));
	p.second = p2.second + (p1.second*p2.first*(1-p2.second))/(1-p1.second*(1-p2.first));
	return p;
}

pair<double,double> getval(int x,int y,int l=0,int r=NV,int k=1) {
	if(x<=l && r<=y) return M[k];
	int m=(l+r)/2;
	if(y<=m) return getval(x,y,l,m,k*2);
	if(x>=m) return getval(x,y,m,r,k*2+1);
	return merge(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
}
void update(int entry, double v) {
	int x,y;
	entry += NV;
	M[entry]={v,v};
	while(entry>1) {
		entry>>=1;
		M[entry] = merge(M[entry*2],M[entry*2+1]);
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q;
	FOR(i,NV*2) M[i]={1,1};
	FOR(i,N) {
		cin>>x>>y;
		P[i]=x*1.0/y;
		update(i,P[i]);
	}
	
	while(Q--) {
		cin>>i;
		if(i==1) {
			cin>>i>>x>>y;
			i--;
			P[i]=x*1.0/y;
			update(i,P[i]);
		}
		else {
			cin>>x>>y;
			_P("%.12lf\n",getval(x-1,y).first);
		}
	}
}

まとめ

まぁそのL(a,c)・R(a,c)を考えるのが難しいよね。