题意：
有n个赌场，你在i赌场时，有pi的概率走到i+1,有1?pi的概率走到i?1.保证任何时候pi≤pi+1
有q次操作，修改一个赌场的p值；或者询问[l,r]表示从第l个赌场走到r的概率,他在走的过程中不会离开区间[l,r].
要点：
比较容易看出是区间树，但是这个概率的处理很复杂，基本思路可以参考下面这个博客：
参考博客：点击打开链接
但是这个博客还有网上我找了一下，有一个地方都没有解释，就是最后结果应该是:
f[l]/f[r]=(g[1]+g[2]...g[l])/(g[1]+g[2]...g[r])=g[1]*(1+t1+t1*t2+...)/(g[1]*((1+t1+t1*t2+...))=(1+t1+t1*t2+...t1*t2..tl)/(1+t1+t1*t2+...t1*t2*tl)=1+(tl+tl*tl+1...)
最后用区间树维护一下即可。
【数据结构|codeforces712E Memory and Casinos（区间树）】
#include
#include
#include
#include
using namespace std;
const int maxn = 100005;
struct segtree
{
double a, b;
}seg[4*maxn],now;
double p[maxn];
int n, q;
void build(int l, int r, int pos)
{
if (l == r)
{
seg[pos].a = seg[pos].b = (1 - p[l]) / p[l];
return;
}
int mid = (l + r) / 2;
build(l, mid, pos*2);
build(mid+1, r, pos * 2 + 1);
seg[pos].a = seg[2 * pos].a*seg[2 * pos + 1].a;
seg[pos].b = seg[2 * pos].b + seg[2 * pos].a*seg[2 * pos + 1].b;
}
void query(int l, int r, int x, int y, int pos)
{
if (l == x&&r == y)
{
now.b = now.b + now.a*seg[pos].b;
now.a = now.a*seg[pos].a;
return;
}
int mid = (l + r) / 2;
if (y <= mid)
query(l, mid, x, y, pos * 2);
else if (x > mid)
query(mid + 1, r, x, y, pos * 2 + 1);
else
{
query(l, mid, x, mid, pos * 2);
query(mid + 1, r, mid + 1, y, pos * 2 + 1);
}
}
void update(int l, int r, int pos, int x)
{
if (l == r)
{
seg[pos].a = seg[pos].b = (1 - p[l]) / p[l];
return;
}
int mid = (l + r) / 2;
if (x <= mid)
update(l, mid, 2 * pos, x);
else
update(mid+1, r, 2 * pos + 1, x);
seg[pos].a = seg[2 * pos].a*seg[2 * pos + 1].a;
seg[pos].b = seg[2 * pos].b + seg[2 * pos].a*seg[2 * pos + 1].b;
}int main()
{
int a, b;
cin >> n >> q;
for (int i = 1;
i <= n;
i++)
{
cin >> a >> b;
p[i] = 1.0*a/b;
}
build(1, n, 1);
while (q--)
{
int order, x, y,z;
cin >> order;
if (order == 2)
{
cin >> x >> y;
now.a = 1;
now.b = 0;
query(1, n, x, y, 1);
double ans;
if (now.b <= 1e15)
ans = 1 / (1 + now.b);
else
ans = 0;
printf("%.10lf\n", ans);
}
else
{
cin >> x >> y >> z;
p[x] = 1.0*y/z;
update(1, n, 1, x);
}
}
return 0;
} 推荐阅读
- 笔记|C语言数据结构——二叉树的顺序存储和二叉树的遍历
- C语言学习(bit)|16.C语言进阶——深度剖析数据在内存中的存储
- 数据结构和算法|LeetCode 的正确使用方式
- 先序遍历 中序遍历 后序遍历 层序遍历
- 数据结构|C++技巧（用class类实现链表）
- 数据结构|贪吃蛇代码--c语言版 visual c++6.0打开
- 算法|算法-二分查找
- 数据结构学习指导|数据结构初阶（线性表）
- leetcode题解|leetcode#106. 从中序与后序遍历序列构造二叉树
- java|ObjectOrientedProgramming - 面向对象的编程（多态、抽象类、接口）- Java - 细节狂魔