# Codeforces 712E 概率+线段树区间合并

17-01-26        来源：[db:作者]

Codeforces 712E 概率+线段树区间合并：现在n个赌场排成一行。在第i个赌场，有p[i]的概率获胜，如果此时i=n则结束，否则到达第i+1个点；有(1-p[i])概率失败，如果此时i=1则结束，否则到达第i-1个点。

- 从第i个赌场开始
- 不能在第i个赌场失败
- 最后在第j个赌场获胜

- 1 i a b 将第i个赌场的胜率改为p[i]=a/b
- 2 l r 询问这个人统治区间[i,j]的概率

(1?≤?n,?q?≤?100?000)

## 4. 实现代码

```#include
using namespace std;

typedef long long LL;
typedef long double LB;
typedef pair PII;
typedef pair PLL;
typedef pair PLB;

const int INF = 0x3f3f3f3f;
const LL INFL = 0x3f3f3f3f3f3f3f3fLL;
const LB eps = 1e-8;
const int MAXN = 100000 + 5;

PLB X[MAXN << 2];

inline PLB calc(const int& a, const int& b) {
LB x = (LB) (b - a) / a;
return make_pair(x, x);
}
inline void pushUp(const int& rt) {
X[rt].first = X[rt << 1].first * X[rt << 1 | 1].first;
X[rt].second = X[rt << 1].second + X[rt << 1 | 1].second * X[rt << 1].first;
}
void build(int l, int r, int rt) {
static int ax, bx;
if(l == r) {
scanf("%d %d", &ax, &bx);
X[rt] = calc(ax, bx);
return;
}
int mid = (l + r) >> 1;
build(l, mid, rt << 1);
build(mid + 1, r, rt << 1 | 1);
pushUp(rt);
}
void update(const int& p, const PLB& v, int l, int r, int rt) {
if(l == r) { X[rt] = v; return; }
int mid = (l + r) >> 1;
if(p <= mid) update(p, v, l, mid, rt << 1);
else update(p, v, mid + 1, r, rt << 1 | 1);
pushUp(rt);
}
PLB query(const int& L, const int& R, int l, int r, int rt) {
static PLB z = make_pair((LB)1.0, (LB)0.0);
if(L <= l && r <= R) return X[rt];
int mid = (l + r) >> 1;
PLB x = z, y = z, ret;
if(L <= mid) x = query(L, R, l, mid, rt << 1);
if(R > mid) y = query(L, R, mid + 1, r, rt << 1 | 1);
ret.first = x.first * y.first;
ret.second = x.second + y.second * x.first;
return ret;
}
int main() {
#ifdef ___LOCAL_WONZY___
freopen("input.txt", "r", stdin);
#endif // ___LOCAL_WONZY___
static int n, q, op, x, ax, bx, lx, rx;
while(~scanf("%d %d", &n, &q)) {
build(1, n, 1);
while(q --) {
scanf("%d", &op);
if(op == 1) {
scanf("%d %d %d", &x, &ax, &bx);
update(x, calc(ax, bx), 1, n, 1);
} else {
scanf("%d %d", &lx, &rx);
LB ans = query(lx, rx, 1, n, 1).second;
if(ans != ans) ans = 0.0; /// 判断是不是nan
else ans = 1 / (1 + ans);
cout << fixed << setprecision(8) << ans << "\n";
}
}
}
return 0;
}```