[ABC332F] Random Update Query 题解

FFTotoro · 2023-12-10 22:03:43 · 题解

对于单独一个元素，考虑一次操作的影响是什么：显然它有 \frac{1}{r-l+1} 的概率被修改为 x，\frac{r-l}{r-l+1} 的概率不变。所以其期望值的变化为 E\leftarrow \frac{E(r-l)}{r-l+1}+\frac{x}{r-l+1}。

对于一个区间上面的操作就是先乘再加，线段树板子。代码中使用 AtCoder Library 实现 modint 与线段树。

放代码：

#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using M=atcoder::modint998244353;
struct S{M a; int s;};
struct F{M a,b;};
S o(S l,S r){return S{l.a+r.a,l.s+r.s};}
S e(){return S{0,0};}
S m(F l,S r){return S{r.a*l.a+r.s*l.b,r.s};}
F c(F l,F r){return F{l.a*r.a,r.b*l.a+l.b};}
F id(){return F{1,0};}
int main(){
  ios::sync_with_stdio(false);
  int n,q; cin>>n>>q;
  vector<S> d(n);
  for(auto &i:d){
    int x; cin>>x; i=S{x,1};
  } // 输入
  atcoder::lazy_segtree<S,o,e,F,m,c,id> t(d);
  while(q--){
    int l,r,x; cin>>l>>r>>x;
    t.apply(l-1,r,F{M(r-l)/M(r-l+1),M(x)/M(r-l+1)});
  } // 更新
  for(int i=0;i<n;i++)
    cout<<t.get(i).a.val()<<' '; // 输出
  cout<<endl;
  return 0;
}