noi.ac 782 【CSP2019模拟 Day 2】a 题解

发表于 | 更新于 | 阅读次数：
本文字数： 1.1k 字 | 阅读时长 ≈ 5 分钟

题意简述

一个长度为$n<=1e5$的序列，支持两种操作：

  1. 等概率随机打乱区间$[l,r]$
  2. 求区间$[l,r]$和的期望值

所有结果（珂能是分数形式）都对$998244353$取膜。

思路

打乱区间$[l,r]$相当于把$l,r$中的数都变成$a[l…r]$的平均值。线段树，区间覆盖区间求和，即珂。

具体思路

为什么这个思路是对的？

随机打乱区间$l,r$，对于$[l,r]$中的某一个数$x$，因为是等概率随机打乱，所以它出现在每一个位置的概率都是相等的，都是$\dfrac{1}{r-l+1}$。所以，$[l,r]$被打乱之后，每个位置的期望都是相等的，它都等于$a[l…r]$的平均值。

那至少区间不重叠的时候，这个算法就正确了。

那么如果我们的区间有重叠怎么办呢？重叠了还正确么？

我们先明确一下期望的概念：$E(x)$表示$x$的期望值，其中$x$是随机变量，而$E(x)$是一个确定的数，表示$x$的期望。

而我们知道，$E(C)=C$，也就是“常数的期望等于本身”。所以$E(E(x))=E(x)$，换句话说，期望套几层都是不变的。

所以我们在期望的基础上求期望，求“期望的期望”，求出来的还是“期望”，不是别的。

所以答案就是正确的了。膜数有点大，记得开$long long$。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
#include <bits/stdc++.h>
using namespace std;
namespace Flandre_Scarlet
{
    #define N 155555
    #define mod 998244353
    #define int long long 
    #define F(i,l,r) for(int i=l;i<=r;++i)
    #define D(i,r,l) for(int i=r;i>=l;--i)
    #define Fs(i,l,r,c) for(int i=l;i<=r;c)
    #define Ds(i,r,l,c) for(int i=r;i>=l;c)
    #define MEM(x,a) memset(x,a,sizeof(x))
    #define FK(x) MEM(x,0)
    #define Tra(i,u) for(int i=G.Start(u),__v=G.To(i);~i;i=G.Next(i),__v=G.To(i))
    #define p_b push_back
    #define sz(a) ((int)a.size())
    #define iter(a,p) (a.begin()+p)
    void R1(int &x)
    {
        x=0;char c=getchar();int f=1;
        while(c<'0' or c>'9') f=(c=='-')?-1:1,c=getchar();
        while(c>='0' and c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
        x=(f==1)?x:-x;
    }
    void Rd(int cnt,...)
    {
        va_list args;
        va_start(args,cnt);
        F(i,1,cnt) 
        {
            int* x=va_arg(args,int*);R1(*x);
        }
        va_end(args);
    }
    class SegmentTree
    //线段树
    //Build(l,r): 建树,区间为l,r
    //Change(l,r,x): 覆盖x在[l,r]上
    //Query(l,r): 询问[l,r]的和
    //好了，请跳到第106行
    {
    public:
        struct node
        {
            int l,r,s,a;
        }tree[N<<2];
        #define ls index<<1
        #define rs index<<1|1

        #define L tree[index].l
        #define R tree[index].r
        #define S tree[index].s
        #define A tree[index].a

        #define lL tree[ls].l
        #define lR tree[ls].r
        #define lS tree[ls].s
        #define lA tree[ls].a

        #define rL tree[rs].l
        #define rR tree[rs].r
        #define rS tree[rs].s
        #define rA tree[rs].a
        void Update(int index=1)
        {
            S=lS+rS;
        }
        void Build(int l,int r,int index=1)
        {
            L=l,R=r;A=-1;
            if (l==r) {R1(S);return;}
            int mid=(l+r)>>1;
            Build(l,mid,ls); Build(mid+1,r,rs);
            Update(index);
        }
        void ChangeOne(int x,int index=1)
        {
            x%=mod;
            A=x;
            S=(x*(R-L+1))%mod;
        }
        void PushDown(int index=1)
        {
            if (A!=-1)
            {
                ChangeOne(A,ls);
                ChangeOne(A,rs);
                A=-1;
            }
        }
        void Change(int l,int r,int x,int index=1)
        {
            if (l>R or L>r) return;
            if (l<=L and R<=r) return ChangeOne(x,index);
            PushDown(index);
            Change(l,r,x,ls); Change(l,r,x,rs);
            Update(index);
        }
        int Query(int l,int r,int index=1)
        {
            if (l>R or L>r) return 0;
            if (l<=L and R<=r) return S;
            PushDown(index);
            return (Query(l,r,ls)+Query(l,r,rs))%mod;
        }
    }T;
    int n,m;
    void Input()
    {
        Rd(2,&n,&m);
        T.Build(1,n);
    }

    int qpow(int a,int b)
    {
        int r=1;
        while(b)
        {
            if (b&1) r=r*a%mod;
            a=a*a%mod,b>>=1;
        }
        return r;
    }
    int mod_div(int a,int b){return a*qpow(b,mod-2)%mod;}
    void Soviet()
    {
        F(i,1,m)
        {
            int o,l,r;Rd(3,&o,&l,&r);
            if (o==1)
            {
                int s=T.Query(l,r)%mod,c=(r-l+1);
                T.Change(l,r,mod_div(s,c));
            }
            if (o==2)
            {
                printf("%lld\n",T.Query(l,r)%mod);
            }
        }
    }

    #define Flan void
    Flan IsMyWife()
    {
        Input();
        Soviet();
    }
    #undef int //long long 
}
int main()
{
    Flandre_Scarlet::IsMyWife();
    getchar();getchar();
    return 0;
}
w