考试的时候切掉了，然而卡精 + 有一个地方忘开 $long long$，完美挂掉 $50$pts.
把式子化简一下，然后直接拿线段树来维护即可.
Code:
// luogu-judger-enable-o2
// luogu-judger-enable-o2
#include <cstdio>
#include <algorithm>
#define N 130304
#define ll double
#define ldb long double
#define setIO(s) freopen(s".in","r",stdin) , freopen(s".out","w",stdout)
using namespace std;
namespace IO
{
char *p1, *p2, buf[100000]; #define nc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1 ++ ) int rd() {
int x = 0, f = 1;
char c = nc();
while (c < 48) {
if (c == '-')
f = -1;
c = nc();
}
while (c > 47) {
x = (((x << 2) + x) << 1) + (c ^ 48), c = nc();
}
return x * f;
}
};
int n,Q;
ll X[N], Y[N];
ll sqr[N],sum[N];
struct Node
{
ll x,y,xy,add_t, add_s, set_s, set_t,sqr;
int set_tag;
}t[N<<2];
inline void pushup(int l,int r,int now)
{
int mid=(l+r)>>1;
if(mid>=l)
{
t[now].x=t[now<<1].x;
t[now].y=t[now<<1].y;
t[now].xy=t[now<<1].xy;
t[now].sqr=t[now<<1].sqr;
}
if(r>mid)
{
t[now].x+=t[now<<1|1].x;
t[now].y+=t[now<<1|1].y;
t[now].xy+=t[now<<1|1].xy;
t[now].sqr+=t[now<<1|1].sqr;
}
}
inline void mark1(int l,int r,int now,ll S,ll T)
{
t[now].add_s+=S, t[now].add_t+=T;
t[now].xy+=(ll)T*t[now].x+(ll)S*t[now].y+(ll)(r-l+1)*S*T;
t[now].sqr+=(ll)2*S*t[now].x+(ll)S*S*(r-l+1);
t[now].x+=(ll)(r-l+1)*S, t[now].y+=(ll)(r-l+1)*T;
}
inline void mark2(int l,int r,int now,ll S,ll T)
{
t[now].set_tag=1, t[now].set_s=S, t[now].set_t=T;
t[now].add_s=t[now].add_t=0;
t[now].x=sum[r]-sum[l-1]+(ll)S*(r-l+1);
t[now].y=sum[r]-sum[l-1]+(ll)T*(r-l+1);
t[now].xy=sqr[r]-sqr[l-1]+(ll)(T+S)*(sum[r]-sum[l-1])+(ll)(r-l+1)*S*T;
t[now].sqr=sqr[r]-sqr[l-1]+(ll)S*S*(r-l+1)+(ll)2*S*(sum[r]-sum[l-1]);
}
inline void pushdown(int l,int r,int now)
{
if(t[now].set_tag)
{
int mid=(l+r)>>1;
if(l<=mid) mark2(l,mid,now<<1,t[now].set_s,t[now].set_t);
if(r>mid) mark2(mid+1,r,now<<1|1,t[now].set_s,t[now].set_t);
t[now].set_s=t[now].set_t=t[now].set_tag=0;
}
if(t[now].add_s || t[now].add_t)
{
int mid=(l+r)>>1;
if(l<=mid) mark1(l,mid,now<<1,t[now].add_s,t[now].add_t);
if(r>mid) mark1(mid+1,r,now<<1|1,t[now].add_s,t[now].add_t);
t[now].add_t=t[now].add_s=0;
}
}
void build(int l,int r,int now)
{
if(l==r)
{
t[now].x=X[l];
t[now].y=Y[l];
t[now].xy=(ll)X[l]*Y[l];
t[now].sqr=(ll)X[l]*X[l];
return;
}
int mid=(l+r)>>1;
if(mid>=l) build(l,mid,now<<1);
if(r>mid) build(mid+1,r,now<<1|1);
pushup(l,r,now);
}
// x+=S, y+=T
void addv(int l,int r,int now,int L,int R,double S,double T)
{
if(l>=L&&r<=R)
{
mark1(l,r,now,S,T);
return;
}
pushdown(l,r,now);
int mid=(l+r)>>1;
if(L<=mid) addv(l,mid,now<<1,L,R,S,T);
if(R>mid) addv(mid+1,r,now<<1|1,L,R,S,T);
pushup(l,r,now);
}
void setv(int l,int r,int now,int L,int R,double S,double T)
{
if(l>=L&&r<=R)
{
mark2(l,r,now,S,T);
return;
}
pushdown(l,r,now);
int mid=(l+r)>>1;
if(L<=mid) setv(l,mid,now<<1,L,R,S,T);
if(R>mid) setv(mid+1,r,now<<1|1,L,R,S,T);
pushup(l,r,now);
}
ll queryx(int l,int r,int now,int L,int R)
{
if(l>=L&&r<=R) return t[now].x;
pushdown(l,r,now);
ll re=0;
int mid=(l+r)>>1;
if(L<=mid) re+=queryx(l,mid,now<<1,L,R);
if(R>mid) re+=queryx(mid+1,r,now<<1|1,L,R);
return re;
}
ll queryy(int l,int r,int now,int L,int R)
{
if(l>=L&&r<=R) return t[now].y;
pushdown(l,r,now);
ll re=0;
int mid=(l+r)>>1;
if(L<=mid) re+=queryy(l,mid,now<<1,L,R);
if(R>mid) re+=queryy(mid+1,r,now<<1|1,L,R);
return re;
}
ll queryxy(int l,int r,int now,int L,int R)
{
if(l>=L&&r<=R) return t[now].xy;
pushdown(l,r,now);
ll re=0;
int mid=(l+r)>>1;
if(L<=mid) re+=queryxy(l,mid,now<<1,L,R);
if(R>mid) re+=queryxy(mid+1,r,now<<1|1,L,R);
return re;
}
ll queryxx(int l,int r,int now,int L,int R)
{
if(l>=L&&r<=R) return t[now].sqr;
pushdown(l,r,now);
ll re=0;
int mid=(l+r)>>1;
if(L<=mid) re+=queryxx(l,mid,now<<1,L,R);
if(R>mid) re+=queryxx(mid+1,r,now<<1|1,L,R);
return re;
}
int main()
{
int i,j,cas;
// setIO("de");
n=IO::rd(),Q=IO::rd();
for(i=1;i<=n;++i) X[i]=IO::rd();
for(i=1;i<=n;++i) Y[i]=IO::rd();
for(i=1;i<=n;++i) sum[i]=sum[i-1]+i, sqr[i]=sqr[i-1]+(ll)i*i;
build(1,n,1);
for(cas=1;cas<=Q;++cas)
{
int opt,l,r,s,t;
opt=IO::rd(),l=IO::rd(),r=IO::rd();
if(opt==1)
{
long double up, down;
long double ybar=queryy(1,n,1,l,r)/(double)(r-l+1);
long double xbar=queryx(1,n,1,l,r)/(double)(r-l+1);
up=(ldb)queryxy(1,n,1,l,r)-ybar*(ldb)queryx(1,n,1,l,r)-xbar*(ldb)queryy(1,n,1,l,r)+(ldb)(r-l+1)*xbar*ybar;
down=(ldb)queryxx(1,n,1,l,r)+xbar*xbar*(ldb)(r-l+1)-2.00*xbar*(ldb)queryx(1,n,1,l,r);
long double answer=up/down;
printf("%.10lf\n",(double)answer);
}
if(opt==2)
{
s=IO::rd(),t=IO::rd();
addv(1,n,1,l,r,s,t);
}
if(opt==3)
{
s=IO::rd(),t=IO::rd();
setv(1,n,1,l,r,s,t);
}
}
return 0;
}
/*
*/