题解 P4927 【[1007]梦美与线段树】
发现这个题还没题解就自己补了吧……
其实这个题最初的idea是我的，然后最初我是按照我去年的一个题P3924 康娜的线段树加强的，唯一的不同其实就是把等概率进入改成了按权重进入。
曾经我想过这个问题，然后还没来得及想清楚我就很菜的退役了，所以这个题等到现在才出出来……
一开始我感觉区间加对于期望的贡献是不太好算的，就打算出成区间乘（这样就是个很傻逼的题了）。然后有一天（在文化课上）闲来无事想到这个题画了一个图，猛然发现分子是都可以被约分掉的，于是这个题就变成了维护一个区间的平方和，考虑如何合并：
当然我最初就是这么写的，辛辛苦苦维护完之后，一个叫做司机（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);
}
}
}