sol：P10338 [THUSC 2019] 彩票

· · 题解

游记节选。

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;
}