题目描述

难度分:$1786$

输入$n(1 \leq n \leq 2 \times 10^5)$，$m(1 \leq m \leq 2 \times 10^5)$和长为$n$的数组$a(0 \leq a[i] \leq 10^9)$。下标从$1$开始。

输入$m$个操作，每次操作输入L R x$(0 \leq x \leq 10^9)$，表示在$[L,R]$中等概率地选一个整数$i$，然后把$a[i]$替换成$x$。

输出最终$a[1],a[2],…,a[n]$的期望值，模$M=998244353$。

注：如果期望值是一个分数$\frac{p}{q}$，你需要输出分数取模结果。

输入样例$1$

5 2
3 1 4 1 5
1 2 2
2 4 0

输出样例$1$

499122179 1 665496238 665496236 5

输入样例$2$

2 4
1 2
1 1 3
2 2 4
1 1 5
2 2 6

输出样例$2$

5 6

输入样例$3$

20 20
998769066 273215338 827984962 78974225 994243956 791478211 891861897 680427073 993663022 219733184 570206440 43712322 66791680 164318676 209536492 137458233 289158777 461179891 612373851 330908158
12 18 769877494
9 13 689822685
6 13 180913148
2 16 525285434
2 14 98115570
14 17 622616620
8 12 476462455
13 17 872412050
14 15 564176146
7 13 143650548
2 5 180435257
4 10 82903366
1 2 643996562
8 10 262860196
10 14 624081934
11 13 581257775
9 19 381806138
3 12 427930466
6 19 18249485
14 19 682428942

输出样例$3$

821382814 987210378 819486592 142238362 447960587 678128197 687469071 405316549 318941070 457450677 426617745 712263899 939619994 228431878 307695685 196179692 241456697 12668393 685902422 330908158

算法

线段树

对于一段区间$[l,r]$，从中选任意一个数$a[i],i \in [l,r]$改成$x$的概率都是$p=\frac{1}{r-l+1}$，因此修改后的期望值为$p \times x+(1-p) \times a[i]$。根据期望的线性性质$E(aX+b)=aE(X)+b$，对于某个$a[i]$，下一次再选到它就以$p \times x+(1-p) \times a[i]$作为原值继续计算。

因此对于每个询问$(l,r,x)$，在区间$[l,r]$上乘以$1-p$再加上$p \times x$就能算出本次操作后的期望。这是个典型的懒标记线段树应用，直接套模板就可以了。

复杂度分析

时间复杂度

建立线段树的时间复杂度为$O(nlog_2n)$；处理$O(m)$个询问，每个询问需要对线段树进行区间修改和查询，时间复杂度为$O(log_2n)$，总的时间复杂度为$O(mlog_2n)$。因此，整个算法的时间复杂度为$O((n+m)log_2n)$。

空间复杂度

空间消耗的瓶颈就是线段树，额外空间复杂度为$O(n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

const int N = 200010, MOD = 998244353;
int n, m, a[N];


class SegmentTree {
public:
    struct Tag {
        LL add, mul;
        Tag() {
            add = 0, mul = 1;
        }
    };

    struct Info {
        int l, r;
        LL sum;
        Tag lazy;
        Info() {}
        Info(int left, int right, int val): l(left), r(right), sum(val) {}
    } tr[N<<2];

    explicit SegmentTree() {}

    void build(int u, int l, int r) {
        if(l == r) {
            tr[u] = Info(l, r, a[l]);
            return;
        }
        int mid = (l + r) >> 1;
        build(lc(u), l, mid);
        build(rc(u), mid + 1, r);
        pushup(u);
    }

    void modify(int l, int r, LL d, LL mu) {
        modify(1, l, r, d, mu);
    }

    Info query(int l, int r) {
        return query(1, l, r);
    }

private:
    int lc(int u) { 
        return u<<1;
    }

    int rc(int u) {
        return u<<1|1;
    }

    void pushup(int u) {
        tr[u] = merge(tr[lc(u)], tr[rc(u)]);
    }

    void pushdown(int u) {
        if(not_null(tr[u].lazy)) {
            down(u);
            clear_lazy(tr[u].lazy);      // 标记下传后要清空
        }
    }

    void modify(int u, int l, int r, LL d, LL mu) {
        if(l <= tr[u].l && tr[u].r <= r) {
            set(u, d, mu);
            return;
        }
        pushdown(u);
        int mid = (tr[u].l + tr[u].r) >> 1;
        if(mid >= l) modify(lc(u), l, r, d, mu);
        if(mid < r) modify(rc(u), l, r, d, mu);
        pushup(u);
    }

    Info query(int u, int l, int r) {
        if(l <= tr[u].l && tr[u].r <= r) return tr[u];
        pushdown(u);
        int mid = (tr[u].l + tr[u].r) >> 1;
        if(r <= mid) {
            return query(u<<1, l, r);
        }else if(mid < l) {
            return query(u<<1|1, l, r);
        }else {
            return merge(query(u<<1, l, r), query(u<<1|1, l, r));
        }
    }

    Info merge(const Info& lchild, const Info& rchild) {
        Info info;
        info.l = lchild.l, info.r = rchild.r;
        info.sum = (lchild.sum + rchild.sum) % MOD;
        return info;
    }

    // modify操作到不能递归时，设置节点的属性值
    void set(int u, LL add, LL mul) {
        int len = tr[u].r - tr[u].l + 1;
        tr[u].sum = (tr[u].sum * mul % MOD + len * add % MOD) % MOD;
        tr[u].lazy.add = (tr[u].lazy.add * mul % MOD + add) % MOD;
        tr[u].lazy.mul = tr[u].lazy.mul * mul % MOD;
    }

    // 下传标记的规则
    void down(int u) {
        set(lc(u), tr[u].lazy.add, tr[u].lazy.mul);
        set(rc(u), tr[u].lazy.add, tr[u].lazy.mul);
    }

    // 判断标记是否为空的规则
    bool not_null(Tag& lazy) {
        return true;    // 注意这个场景下没法判空
    }

    // 清空标记的规则
    void clear_lazy(Tag& lazy) {
        lazy.add = 0;
        lazy.mul = 1;
    }
};

int fast_power(int a, int b, int p) {
    int res = 1 % p;
    while(b) {
        if(b & 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        b >>= 1;
    }
    return res;
}

int main() {
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    SegmentTree seg;
    seg.build(1, 1, n);
    while(m--) {
        int l, r, x;
        scanf("%d%d%lld", &l, &r, &x);
        LL inv = fast_power(r - l + 1, MOD - 2, MOD);
        seg.modify(l, r, x * inv % MOD, (r - l) * inv % MOD);
    }
    for(int i = 1; i <= n; i++) {
        printf("%d ", seg.query(i, i).sum);
    }
    return 0;
}