自动搬运

查看原文

来自洛谷，原作者为

	zcysky 消え去る花かがやく息吹

搬运于2025-08-24 22:05:21，当前版本为作者最后更新于2018-10-08 21:50:14，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

发现这个题还没题解就自己补了吧……

其实这个题最初的idea是我的，然后最初我是按照我去年的一个题P3924 康娜的线段树加强的，唯一的不同其实就是把等概率进入改成了按权重进入。

曾经我想过这个问题，然后还没来得及想清楚我就很菜的退役了，所以这个题等到现在才出出来……

一开始我感觉区间加对于期望的贡献是不太好算的，就打算出成区间乘（这样就是个很傻逼的题了）。然后有一天（在文化课上）闲来无事想到这个题画了一个图，猛然发现分子是都可以被约分掉的，于是这个题就变成了维护一个区间的平方和，考虑如何合并：$(a+b)^2=a^2+b^2+2ab$，对这三项分开来维护就好了。

当然我最初就是这么写的，辛辛苦苦维护完之后，一个叫做司机（mcfx）的毒瘤发现了这个题其实可以在取模之前爆掉long long，然后另一个叫做ComeIntoPower的毒瘤就顺手改了数据把我卡了。

所以把下面的代码改成__uint128就能过了。然而yfz在造数据的时候似乎没卡掉int128

所以司机和小圆强无敌！

#include<bits/stdc++.h>
#define lson (o<<1)
#define rson (o<<1|1)
#define fi first
#define sc second
#define dbg(x) cout<<#x<<" = "<<(x)<<endl;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef  __uint128_t ulll;
using namespace std;
const double pi=acos(-1);
const double eps=1e-6;
inline int lowbit(int x){return x&(-x);}
inline int read(){
    int f=1,x=0;char ch;
    do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');
    do{x=x*10+ch-'0';ch=getchar();}while(ch>='0'&&ch<='9');
    return f*x;
}
template<typename T> inline T max(T x,T y,T z){return max(max(x,y),z);}
template<typename T> inline T min(T x,T y,T z){return min(min(x,y),z);}
template<typename T> inline T sqr(T x){return x*x;}
template<typename T> inline void checkmax(T &x,T y){x=max(x,y);}
template<typename T> inline void checkmin(T &x,T y){x=min(x,y);}
template<typename T> inline void read(T &x){
x=0;T f=1;char ch;do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');
do x=x*10+ch-'0',ch=getchar();while(ch<='9'&&ch>='0');x*=f;
}
template<typename A,typename B,typename C> inline A fpow(A x,B p,C yql){
    A ans=1;
    for(;p;p>>=1,x=1LL*x*x%yql)if(p&1)ans=1LL*x*ans%yql;
    return ans;
}
struct FastIO{
    static const int S=1310720;
    int wpos;char wbuf[S];
    FastIO():wpos(0) {}
    inline int xchar(){
        static char buf[S];
        static int len=0,pos=0;
        if(pos==len)pos=0,len=fread(buf,1,S,stdin);
        if(pos==len)return -1;
        return buf[pos++];
    }
    inline int read(){
        int c=xchar(),x=0;
        while(c<=32&&~c)c=xchar();
        if(c==-1)return -1;
        for(;'0'<=c&&c<='9';c=xchar())x=x*10+c-'0';
        return x;
    }
}io;
//#define read io.read
const int N=100100;
const int yql=998244353;
inline int orzyql(int x){return x>=yql?x-yql:x;}
ulll ax[N<<2],ab[N<<2],bx[N<<2],addv[N<<2],size[N<<2],sumv[N<<2];
int n,m,a[N];
inline void merge(int o,int l,int r){
    ax[o]=orzyql(ax[lson]+ax[rson]);
    bx[o]=orzyql(bx[lson]+bx[rson]);
    ab[o]=orzyql(ab[lson]+ab[rson]);
    ax[o]=(ax[o]+1LL*(r-l+1)*(r-l+1))%yql;
    bx[o]=(bx[o]+1LL*sumv[o]*sumv[o])%yql;
    ab[o]=(ab[o]+2LL*(r-l+1)*sumv[o])%yql;
}
inline void pushup(int o,int l,int r){
    sumv[o]=orzyql(sumv[lson]+sumv[rson]);
    merge(o,l,r);
}
inline void pushdown(int o,int l,int r){
    if(!addv[o])return;
    int mid=(l+r)>>1;
    sumv[lson]=(sumv[lson]+1LL*(mid-l+1)*addv[o]%yql)%yql;
    sumv[rson]=(sumv[rson]+1LL*(r-mid)*addv[o]%yql)%yql;
    addv[lson]=orzyql(addv[lson]+addv[o]);
    addv[rson]=orzyql(addv[rson]+addv[o]);
    bx[lson]=(1LL*addv[o]*addv[o]%yql*ax[lson]+1LL*addv[o]*ab[lson]%yql+bx[lson])%yql;
    bx[rson]=(1LL*addv[o]*addv[o]%yql*ax[rson]+1LL*addv[o]*ab[rson]%yql+bx[rson])%yql;
    ab[lson]=(2LL*addv[o]*ax[lson]%yql+ab[lson])%yql;
    ab[rson]=(2LL*addv[o]*ax[rson]%yql+ab[rson])%yql;
    addv[o]=0;
}
inline void build(int o,int l,int r){
    if(l==r){
        sumv[o]=a[l];
        ax[o]=1;bx[o]=1LL*a[l]*a[l]%yql;
        ab[o]=2LL*a[l]%yql;
        return;
    }
    int mid=(l+r)>>1;
    build(lson,l,mid);
    build(rson,mid+1,r);
    pushup(o,l,r);
}
inline void optadd(int o,int l,int r,int ql,int qr,int v){
    if(ql<=l&&r<=qr){
        sumv[o]=(sumv[o]+1ll*(r-l+1)*v)%yql;
        addv[o]=orzyql(addv[o]+v);
        bx[o]=(1LL*v*v%yql*ax[o]+1LL*v*ab[o]%yql+bx[o])%yql;
        ab[o]=(2LL*v*ax[o]%yql+ab[o])%yql;
        return;
    }
    int mid=(l+r)>>1;
    pushdown(o,l,r);
    if(ql<=mid)optadd(lson,l,mid,ql,qr,v);
    if(qr>mid)optadd(rson,mid+1,r,ql,qr,v);
    pushup(o,l,r);
}
int main(){
    n=read();m=read();
    for(int i=1;i<=n;i++)a[i]=read();
    build(1,1,n);
    while(m--){
        int opt=read();
        if(opt==2)printf("%lld\n",1LL*bx[1]*fpow(sumv[1],yql-2,yql)%yql);
        else{
            int l=read(),r=read(),v=read();
            optadd(1,1,n,l,r,v);
        }
    }
}