自动搬运

查看原文

来自洛谷，原作者为

	流水行船CCD 果 果 没 有 特 权 ~

搬运于2025-08-24 22:57:04，当前版本为作者最后更新于2024-05-04 16:28:12，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

游记节选。

P10338 [THUSC 2019] 彩票

经典概型的有趣题。

• 一操作。

难点在于一操作。

这题有个非常重要且有趣的性质：如果只考虑一操作，不妨令 $P_{i,j}$ 表示第 $i$ 号箱子抽第 $j$ 次奖抽出中奖卷的概率（注意这里是第 $j$ 次，而非前 $j$ 次），令 $i$ 号奖箱期望拥有 $x$ 张中奖卷，$y$ 张空奖卷，则有：

$$P_{i,1} = \frac{x}{x+y}$$ $$P_{i,2} = \frac{x}{x+y} \times \frac{x-1}{x+y-1} + \frac{y}{x+y} \times \frac{x}{x+y-1} = \frac{x}{x+y} $$$$P_{i,3} = \frac{x}{x+y} \times \dots = \frac{x}{x+y} $$

我们发现，无论当前抽取的是第几次，中奖概率恒为最开始的 $\frac{x}{x+y}$。 于是抽取 $c$ 次可以期望抽出 $c \times \frac{x}{x+y}$ 张中奖卷，这个可以用快速幂求逆元 $O(\log V)$ 计算。而这个操作使用线段树即可快速维护求解。（这里每次抽奖后不需要改每个元素的初始 $x,y$，因为正如上文，在没有加奖的情况下，无论抽多少次，其概率都只用初始 $x,y$ 计算）

但是这道题并没有这么简单。发现有一种情况我们没有考虑：就是有箱子被抽空的时候，这时我们抽出中奖卷的期望就是其拥有中奖卷的个数 $x$，初始 $x,y$ 也要被置为 $0$。（因为之后的概率会变为 $0$）也就是说，我们只能批量更改所有 $x+y > c$ 的元素，看似无法维护。但是如果你学过 segment tree beats（吉司机线段树），就会发现这其实是可以摊还分析的。

姑且不考虑三操作，假设初始势能为所有奖箱中奖卷个数 $>0$ 的奖箱个数，设为 $\Phi_0 \le N$，设当前的一操作有 $x$ 个奖箱的奖卷个数 $\le c$，则 $\Phi_i = \Phi_{i-1} - x$，因为这 $x$ 个奖箱都会被抽成 $0$ 张奖卷。发现势能在减少，而总势能不超过 $N$，所有暴力改的奖箱时间复杂度摊还 $O(N \log N)$。

• 二操作。

求出每一个箱子抽出中奖卷的期望，并把信息存储在一颗线段树上，只需要一个区间求和就可以在 $O(\log N)$ 内快速回答询问。

• 三操作。

真不知道为什么会给没有三操作的部分分？三操作比一操作简单很多。发现如果我们维护每一个箱子剩余中奖卷和空奖卷的期望个数，只用给对应个数加上加奖的值，然后用新的期望去更新一操作对应节点初始计算概率时的初始 $x,y$。

也许有人会问：三操作不是会增加势能吗？这样一操作时间复杂度不久不对了吗？但是三操作是单点修改！每次三操作势能顶多增加 $1$，总共只有 $Q$ 次，总势能为 $\Phi = n + Q$，摊还 $O((N+Q) \log N)$ 仍然可以接受。

自此，得到一个 $O((N+Q)\log N + (N+Q) \log V)$ 的优美算法。（有求逆元的时间复杂度）

$\tt AC\ Code$

#include<bits/stdc++.h>

#define REP(i, l, r) for (int i = l; i <= r; ++i)
#define PER(i, l, r) for (int i = l; i >= r; --i)
#define int long long
#define ull unsigned long long

using namespace std;

const int N = 3e5 + 7;
const int inf = 1e12 + 9;
const int mod = 1e9 + 7;

namespace wyy {
	int n, q, A[N], B[N];
	inline int qpow(int x, int y) {
		int Res = 1; x %= mod;
		while (y) {
			if (y & 1) Res = (Res * x) % mod;
			x = (x * x) % mod;
			y >>= 1;
		} return Res;
	}
	struct Node {
		int a, mi, ma, len, Ans, tg;
      //mi 区间奖箱最少拥有奖卷数
      //ma 区间奖箱最多拥有奖卷数
      //len 区间初始 (x)/(x+y) 概率和，用于计算区间期望
      //Ans 区间期望值
      //tg 区间抽 tg 次奖懒标记
		Node() {
			mi = inf, ma = Ans = tg = len = a = 0;
		}
#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)
	} tr[N << 2];
	inline void pushup(int x) {
		tr[x].a = (tr[ls(x)].a + tr[rs(x)].a) % mod;
		tr[x].mi = min(!tr[ls(x)].ma ? inf : tr[ls(x)].mi, !tr[rs(x)].ma ? inf : tr[rs(x)].mi);
		tr[x].ma = max(tr[ls(x)].ma, tr[rs(x)].ma);
		tr[x].len = (tr[ls(x)].len + tr[rs(x)].len) % mod;
		tr[x].Ans = (tr[ls(x)].Ans + tr[rs(x)].Ans) % mod;
	}
	inline void pdd(int x ,int tg) {
		if (!tr[x].ma) return;
		tr[x].tg += tg;
		tr[x].mi -= tg, tr[x].ma -= tg;
		tr[x].a = (tr[x].a - tr[x].len * tg % mod + mod) % mod;
		tr[x].Ans = (tr[x].Ans + tr[x].len * tg) % mod;
	}
	inline void pushdown(int x) {
		if (tr[x].tg) {
			pdd(ls(x), tr[x].tg), pdd(rs(x), tr[x].tg);
			tr[x].tg = 0;
		}
	}
	inline void Build(int x, int l, int r) {
		if (l == r) {
			tr[x].a = A[l];
			tr[x].mi = tr[x].ma = A[l] + B[l];
			tr[x].len = A[l] * qpow(tr[x].ma, mod - 2) % mod;
			return;
		} int mid = (l + r) >> 1;
		Build(ls(x), l, mid);
		Build(rs(x), mid + 1, r);
		pushup(x);
	}
	inline int Ask(int x, int l, int r, int L, int R) {
		if (L <= l && r <= R) return tr[x].Ans;
		int mid = (l + r) >> 1, c = 0; pushdown(x);
		if (L <= mid) c = Ask(ls(x), l, mid, L, R);
		if (mid < R) c = (c + Ask(rs(x), mid + 1, r , L, R)) % mod;
		return c;
	}
	inline void Chk(int x, int l, int r, int L, int R, int c) {//摊还 O(log)
		if (!tr[x].ma) return;
		if (L <= l && r <= R) {
			if (tr[x].mi > c) {pdd(x, c); return;}//全都抽不完
			if (l == r) {//直接抽完
				tr[x].Ans = (tr[x].Ans + tr[x].a) % mod;
				tr[x].a = tr[x].ma = tr[x].mi = tr[x].len = 0;
				return;
			}
		} int mid = (l + r) >> 1; pushdown(x);
		if (L <= mid) Chk(ls(x), l, mid, L, R, c);
		if (mid < R) Chk(rs(x), mid + 1, r, L, R, c);
		pushup(x);
	}
	inline void modify(int x, int l, int r, int now, int a, int b) {
		if (l == r) {
			tr[x].a = (tr[x].a + a) % mod;
			tr[x].mi += a + b, tr[x].ma += a + b;
			tr[x].len = tr[x].a * qpow(tr[x].ma, mod - 2) % mod;
			return;
		} int mid = (l + r) >> 1; pushdown(x);
		if (now <= mid) modify(ls(x), l, mid, now, a, b);
		else modify(rs(x), mid + 1, r, now, a, b);
		pushup(x);
	}
	signed main() {
		cin >> n >> q; int op, x, y, z;
		REP(i, 1, n) cin >> A[i] >> B[i];
		Build(1, 1, n);
		REP(i, 1, q) {
			cin >> op >> x >> y;
			if (op == 1) {
				cin >> z;
				Chk(1, 1, n, x, y, z);
			} else if (op == 2) {
				cout << Ask(1, 1, n, x, y) << '\n';
			} else {
				cin >> z;
				modify(1, 1, n, x, y, z);
			}
		}
		return 0;
	}
} 
signed main() {
// 	freopen("lottery.in", "r", stdin);
// 	freopen("lottery.out", "w", stdout);
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	wyy::main(); 
	return 0;
}