WA on #8 #9 #10,why?
#include<cmath>
#include<vector>
#include<complex>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;
char buf[1<<20], *p1=buf, *p2=buf;
#define getchar() (p1==p2&&(p2=buf+fread(p1=buf, 1, 1<<20, stdin), p1==p2)?EOF:*p1++)
template <typename T>
void read(T &x)
{
x=0;int f=1;char c=getchar();
while (!isdigit(c)) f=(c=='-')?-1:1, c=getchar();
while (isdigit(c)) x=(x<<1)+(x<<3)+c-'0', c=getchar();
x*=f;
}
typedef double LD;
const int N=1e5+10;
int n, m;LD x[N], y[N];
struct node{LD mul, sx, vx, vy;};
struct trnode
{
int l, r;
LD tagx, tagy, cov, mul, vx, vy, sx;
trnode() {tagx=tagy=cov=mul=vx=vy=sx=0;}
}tr[N<<3];
LD f(int x) {return x*(x+1)*(2*x+1)/6;}
LD get(int l, int r) {return f(r)-f(l-1);}
node operator +(const node &n1, const node &n2)
{
node res;
res.mul=n1.mul+n2.mul;
res.sx=n1.sx+n2.sx;
res.vx=n1.vx+n2.vx;
res.vy=n1.vy+n2.vy;
return res;
}
void add(int p, LD S, LD T)
{
int l=tr[p].l, r=tr[p].r;
tr[p].mul+=S*tr[p].vy+T*tr[p].vx+(r-l+1)*1.0*S*T;
tr[p].sx+=2.0*S*tr[p].vx+(r-l+1)*1.0*S*S;
tr[p].vx+=(r-l+1)*1.0*S;tr[p].vy+=(r-l+1)*1.0*T;
tr[p].tagx+=S, tr[p].tagy+=T;
}
void cover(int p)
{
int l=tr[p].l, r=tr[p].r;
tr[p].mul=tr[p].sx=get(l, r);
tr[p].vx=tr[p].vy=(l+r)*(r-l+1)/2.0;
tr[p].tagx=tr[p].tagy=0;tr[p].cov=1;
}
void pushup(int p)
{
tr[p].mul=tr[p<<1].mul+tr[p<<1|1].mul;
tr[p].vx=tr[p<<1].vx+tr[p<<1|1].vx;
tr[p].vy=tr[p<<1].vy+tr[p<<1|1].vy;
tr[p].sx=tr[p<<1].sx+tr[p<<1|1].sx;
}
void build(int p, int l, int r)
{
tr[p].l=l, tr[p].r=r;
if (l==r)
{
tr[p].vx=x[l], tr[p].vy=y[l];
tr[p].sx=x[l]*x[l], tr[p].mul=x[l]*y[l];
}
else
{
int mid=(l+r)>>1;
build(p<<1, l, mid), build(p<<1|1, mid+1, r);
pushup(p);
}
}
void pushdown(int p)
{
if (tr[p].cov)
{
cover(p<<1), cover(p<<1|1);
tr[p].cov=0;
}
if (tr[p].tagx||tr[p].tagy)
{
LD tagx=tr[p].tagx, tagy=tr[p].tagy;
add(p<<1, tagx, tagy), add(p<<1|1, tagx, tagy);
tr[p].tagx=tr[p].tagy=0;
}
}
void change1(int p, int l, int r, LD S, LD T)
{
if (l<=tr[p].l&&tr[p].r<=r)
{
add(p, S, T);
return ;
}
pushdown(p);
int mid=(tr[p].l+tr[p].r)>>1;
if (l<=mid) change1(p<<1, l, r, S, T);
if (r>mid) change1(p<<1|1, l, r, S, T);
pushup(p);
}
void change2(int p, int l, int r, LD S, LD T)
{
if (l<=tr[p].l&&tr[p].r<=r)
{
cover(p), add(p, S, T);
return ;
}
pushdown(p);
int mid=(tr[p].l+tr[p].r)>>1;
if (l<=mid) change2(p<<1, l, r, S, T);
if (r>mid) change2(p<<1|1, l, r, S, T);
pushup(p);
}
node query(int p, int l, int r)
{
if (l<=tr[p].l&&tr[p].r<=r) return {tr[p].mul, tr[p].sx, tr[p].vx, tr[p].vy};
pushdown(p);
int mid=(tr[p].l+tr[p].r)>>1;node res={0, 0, 0, 0};
if (l<=mid) res=res+query(p<<1, l, r);
if (r>mid) res=res+query(p<<1|1, l, r);
pushup(p);return res;
}
int main()
{
scanf("%d%d", &n, &m);
for (int i=1;i<=n;i++) scanf("%lf", &x[i]);
for (int i=1;i<=n;i++) scanf("%lf", &y[i]);
build(1, 1, n);
for (int i=1;i<=m;i++)
{
int op, l, r;LD S, T;
scanf("%d%d%d", &op, &l, &r);
if (op==1)
{
node res=query(1, l, r);
LD avgx=res.vx/((r-l+1)*1.0), avgy=res.vy/((r-l+1)*1.0);
LD ans1=res.mul-avgx*res.vy-avgy*res.vx+(r-l+1)*1.0*avgx*avgy;
LD ans2=res.sx-2.0*avgx*res.vx+(r-l+1)*1.0*avgx*avgx;
printf("%.10lf\n", ans1/ans2);
}
else if (op==2) scanf("%lf%lf", &S, &T), change1(1, l, r, S, T);
else scanf("%lf%lf", &S, &T), change2(1, l, r, S, T);
}
return 0;
}
感觉像是区间覆盖的错,但是找不出来qaq