頻道欄目
首頁 > 資訊 > 其他綜合 > 正文

【Codeforces Round 370 (Div 2) E】【線段樹 等比數列 區間合并】Memory and Casinos 賭場區間[l,r] l進r先出的概率

16-09-29        來源:[db:作者]  
收藏   我要投稿
E. Memory and Casinos time limit per test 4 seconds memory limit per test 512 megabytes input standard input output standard output

There arencasinos lined in a row. If Memory plays at casinoi, he has probabilitypito win and move to the casino on the right (i?+?1) or exit the row (ifi?=?n), and a probability1?-?pito lose and move to the casino on the left (i?-?1) or also exit the row (ifi?=?1).

We say that Memorydominateson the intervali...jif he completes a walk such that,

  • He starts on casinoi.
  • He never looses in casinoi.
  • He finishes his walk by winning in casinoj.

Note that Memory can still walk left of the1-st casino and right of the casinonand that always finishes the process.

Now Memory has some requests, in one of the following forms:

  • 1iab: Set.
  • 2lr: Print the probability that Memory willdominateon the intervall...r, i.e. compute the probability that Memory will first leave the segmentl...rafter winning at casinor, if she starts in casinol.

It is guaranteed that at any moment of timepis anon-decreasing sequence, i.e.pi?≤?pi?+?1for allifrom1ton?-?1.

Please help Memory by answering all his requests!

Input

The first line of the input contains two integersnandq(1?≤?n,?q?≤?100?000), — number of casinos and number of requests respectively.

The nextnlines each contain integersaiandbi(1?≤?ai?bi?≤?109) —is the probabilitypiof winning in casinoi.

The nextqlines each contain queries of one of the types specified above (1?≤?a?b?≤?109,1?≤?i?≤?n,1?≤?l?≤?r?≤?n).

It's guaranteed that there will be at least one query of type2, i.e. the output will be non-empty. Additionally, it is guaranteed thatpforms a non-decreasing sequence at all times.

Output

Print a real number for every request of type2— the probability that boy will "dominate" on that interval. Your answer will be considered correct if its absolute error does not exceed10?-?4.

Namely: let's assume that one of your answers isa, and the corresponding answer of the jury isb. The checker program will consider your answer correct if|a?-?b|?≤?10?-?4.

Example input
3 13
1 3
1 2
2 3
2 1 1
2 1 2
2 1 3
2 2 2
2 2 3
2 3 3
1 2 2 3
2 1 1
2 1 2
2 1 3
2 2 2
2 2 3
2 3 3
output
0.3333333333
0.2000000000
0.1666666667
0.5000000000
0.4000000000
0.6666666667
0.3333333333
0.2500000000
0.2222222222
0.6666666667
0.5714285714
0.6666666667

 

 

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
void fre() { freopen("c://test//input.in", "r", stdin); freopen("c://test//output.out", "w", stdout); }
#define MS(x,y) memset(x,y,sizeof(x))
#define MC(x,y) memcpy(x,y,sizeof(x))
#define MP(x,y) make_pair(x,y)
#define ls o<<1
#define rs o<<1|1
#define lson o<<1,l,mid
#define rson o<<1|1,mid+1,r
#define ff first
#define ss second
typedef long long LL;
typedef unsigned long long UL;
typedef unsigned int UI;
typedef pair PD;
template inline void gmax(T1 &a, T2 b) { if (b>a)a = b; }
template inline void gmin(T1 &a, T2 b) { if (b> 1;
	build(lson);
	build(rson);
	a[o] = merge(a[ls], a[rs]);
}
PD V; int P;
void update(int o, int l, int r)
{
	if (l == r)
	{
		a[o] = V;
		return;
	}
	int mid = (l + r) >> 1;
	if (P <= mid)update(lson);
	else update(rson);
	a[o] = merge(a[ls], a[rs]);
}
int L, R;
PD query(int o, int l, int r)
{
	if (l >= L&&r <= R)return a[o];
	int mid = (l + r) >> 1;
	if (R <= mid)return query(lson);
	else if (L > mid)return query(rson);
	else return merge(query(lson), query(rson));
}
int main()
{
	while (~scanf("%d%d", &n, &q))
	{
		build(1, 1, n);
		while (q--)
		{
			int op; scanf("%d", &op);
			if (op == 1)
			{
				double x, y;
				scanf("%d%lf%lf", &P, &x, &y);
				V = { x / y,x / y };
				update(1, 1, n);
			}
			else
			{
				scanf("%d%d", &L, &R);
				printf("%.12f\n", query(1, 1, n).ff);
			}
		}
	}
	return 0;
}
/*
【題意】
有n(1e5)個賭場,我們一開始在1號賭場,
在第i個賭場賭贏的概率為p[i]
如果賭贏了,會進入第i+1個賭場
如果賭輸了,會進入第i-1個賭場

有m(1e5)個詢問,
問你,對于詢問區間[l,r]
如果我們從l位置開始賭博,第一次走出[l,r]區間是因為r贏而不是因為l輸的概率是多少。

【類型】
線段樹 等比數列 區間合并

【分析】
我們要求的是對于區間[l,r],從l位置開始賭博,第一次走出[l,r]區間是因為r贏而不是因為l輸的概率是多少。
我們設其為L[l,r],顯然第一次是從[l,r]的l輸走出區間的概率是1-L[l,r]

這個問題乍一想很難,但是我們可以從中捕捉到區間合并的影子。
我們考慮已經直到了[l,mid]和[mid+1,r]兩個區間內部的屬性,并嘗試合并。

我們把L[l,mid]設為l1,把L[mid+1,r]設為l2.
那么,我們考慮從mid->mid+1經過了1次,2次,3次,...
其概率公式分別是
l1 * l2
l1 * (1-l2) * probability of [ mid處進入[l,mid],mid處第一次出[l,mid]]

于是我們需要:
對于區間[l,r],從r位置開始賭博,第一次走出[l,r]區間是因為r贏而不是因為l輸的概率為R[l,r]。
把R[l,mid]設為r1,把R[mid+1,r]設為r2.
那么之前的概率公式變成了——
l1 * l2
l1 * (1-l2) * r1 * l2
l1 * ((1-l2) * r1)^2 * l2
...
a1=l1*l2
q=((1-l2)*r1)
無窮多項求和=a1/(1-q)

我們還要求R
我們考慮從mid->mid+1經過了0次,1次,2次,3次,...
其概率公式分別是
r2
(1-r2) * r1 * l2
(1-r2) * r1 * (1 - l2) * r1 * l2
(1-r2) * r1 * ((1 - l2) * r1)^2 * l2
一樣求和即可

于是對于詢問,我們可以用線段樹維護區間L和R并合并,最后得到答案。

【時間復雜度&&優化】
O(qlogn)

*/
相關TAG標簽
上一篇:臺積電:絕大多數7nm客戶都會轉向6nm_IT新聞_博客園
下一篇:最后一頁
相關文章
圖文推薦

關于我們 | 聯系我們 | 廣告服務 | 投資合作 | 版權申明 | 在線幫助 | 網站地圖 | 作品發布 | Vip技術培訓 | 舉報中心

版權所有: 紅黑聯盟--致力于做實用的IT技術學習網站

美女MM131爽爽爽毛片