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

题意简述

一个长度为$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$。

代码

复制

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