【题解】SS221101C.iiidx

题目链接

题目描述

有一个长度为 \(n\) 的01序列，第 \(i\) 个位置有 \(p_i\) 的概率为1，对于上面的一段 \(l\sim r\) 的区间，现在有两种计算方式（\(A,B,t\) 都是给定的值）：

\[\text{基本分}=A\times\sum_{i=l}^r s_i\\ \text{毗连分}=B\times(\sum_{i=l}^r s_i\cdot f(i))\\ f(i) = \begin{cases} s_i & i = l \\ f(i-1) + 1 & i \neq l \land S_i = 1 \\ f(i-1) \times t & \text{otherwise} \end{cases} \]

现在你需要支持两种操作，单点修改概率 和 区间求基本分与毗连分的和的期望。
\(n,q\le 5\times10^5\)

题解

有期望的线性性可以拆成基本分和毗连分两个分别算期望，基本分非常好算：

\[E[\text{基本分}]=E[A\times\sum_{i=l}^r s_i]=A\times\sum_{i=l}^r p_i \]

这个显然可以用树状数组维护。

毗连分比较困难：

\[E[\text{毗连分}]=B\times(\sum_{i=l}^r f(i)\cdot p_i) \]

考虑将其拆成贡献形式，我们发现 \(i,j(i\le j)\) 之间是一个只有 \(t\) 的一个若干次多项式，我们钦定 \(i,j\) 是1来统计答案，我们只考虑从 \(i\) 开始的 \(t\) 到 \(j\) 的贡献，考虑在 \([i+1,j-1]\) 这段区间的数，如果为1，则贡献 \(\times 1\)，否则可以 \(\times t\)，于是枚举 \(i,j\) 统计贡献，可以写出这样的式子：

\[\sum_{i=l}^r\sum_{j=i+1}^rp_ip_j\prod_{k=i+1}^{j-1}g_k\\ g_k=p_k\times1+(1-p_k)\times t。 \]

附注：这里只考虑从当前的 \(i\) 到 \(j\) 单项 \(t\) 的贡献，其他项的贡献在枚举其他 \(i,j\) 是自然会统计。（这应该是计数常见的一个trick吧****

然后我们发现，这个式子可以用线段树维护，具体如何维护呢？我们发现我们求的每段贡献都长成这个样子:

\[p_i\cdot g_{i+1}\cdots g_{j-1}\cdot p_j \]

那么我们可以类比线段树维护区间子段和，难点在于pushup，对于线段树上区间 \(l,r\) 维护 \(sl=p_l\cdot g_{l+1}\cdots g_r\) 维护\(sr=g_l\cdots g_{r-1}\cdot p_r\)，在维护答案，将子段和的取 \(\max\) 类比转化为答案累加，为了方便还可以维护一个 \(pw=g_l\cdots g_r\)。

code of pushup

struct node {int sl, sr, s, pw;node operator + (const node &x) {return {(sl + x.sl * pw % mod) % mod, (sr * x.pw % mod + x.sr) % mod,(s + x.s + sr * x.sl % mod) % mod, pw * x.pw % mod};}
}sgt[N << 2];

剩下的就很简单啦！

完整代码

#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define out() (cout << "sb\n")
#define int llconst int N = 5e5 + 5, mod = 998244353;int qpow(int a, int b) {int ans = 1;for (; b; b >>= 1) {if (b & 1) ans = ans * a % mod;a = a * a % mod;}return ans;
}int idx, n, q, A, B, t, ta, tb, p[N];
int bt[N];void add(int pos, int x) {x %= mod;for (int i = pos; i <= n; i += i & -i) bt[i] = (bt[i] + x + mod) % mod;
}
int qry(int pos) {int ans = 0;for (int i = pos; i >= 1; i -= i & -i) ans = (ans + bt[i]) % mod;return ans;
}
int qry(int l, int r) {return (qry(r) - qry(l - 1) + mod) % mod;
}struct node {int sl, sr, s, pw;node operator + (const node &x) {return {(sl + x.sl * pw % mod) % mod, (sr * x.pw % mod + x.sr) % mod,(s + x.s + sr * x.sl % mod) % mod, pw * x.pw % mod};}
}sgt[N << 2];#define ls (u << 1)
#define rs (u << 1 | 1)
#define mid (beg + en >> 1)void pushup(int u) {sgt[u] = sgt[ls] + sgt[rs];
}
void mk(int u, int x) {sgt[u].sl = sgt[u].sr = x;sgt[u].pw = (x + (1 - x) * t % mod + mod) % mod;
}
void bld(int u, int beg, int en) {if (beg == en) {mk(u, p[beg]);return;}bld(ls, beg, mid);bld(rs, mid + 1, en);pushup(u);
}
void mdf(int u, int beg, int en, int pos) {if (beg == en) {mk(u, p[beg]);return;}if (pos <= mid) mdf(ls, beg, mid, pos);else mdf(rs, mid + 1, en, pos);pushup(u);
}
node qry(int u, int beg, int en, int l, int r) {if (beg >= l && en <= r) return sgt[u];if (r <= mid)return qry(ls, beg, mid, l, r);else if (l > mid)return qry(rs, mid + 1, en, l, r);elsereturn qry(ls, beg, mid, l, mid) + qry(rs, mid + 1, en, mid + 1, r);
}signed main(){freopen("iiidx.in", "r", stdin);freopen("iiidx.out", "w", stdout);IOS;cin >> idx >> n >> q >> ta >> tb >> A >> B;t = ta * qpow(tb, mod - 2) % mod;for (int i = 1; i <= n; i++) {int x, y;cin >> x >> y;p[i] = x * qpow(y, mod - 2) % mod;}bld(1, 1, n);for (int i = 1; i <= n; i++) add(i, p[i]);while (q--) {int op, pos, wa, wb, w, l, r;cin >> op;if (op == 0) {cin >> pos >> wa >> wb;w = wa * qpow(wb, mod - 2) % mod;add(pos, (w - p[pos] + mod) % mod);p[pos] = w;mdf(1, 1, n, pos);} else {cin >> l >> r;cout << (qry(l, r) * (A + B) % mod + qry(1, 1, n, l, r).s * B % mod + mod) % mod << "\n";}}return 0;
}