把两个式子拆开
Σ（xi-px）（yi-py） =Σ xiyi + py * Σ xi - px * Σ yi + Σ 1* px * py
Σ （xi-px）² = Σ xi² + px * Σ xi * 2 + Σ 1* px²
用线段树维护 Σxiyi ， Σxi ，Σ yi ， Σ xi²
同时维护两个标记：增加和修改
对于增加操作，假设给x增加a，给y增加b
Σ （xi+a）（yi+b）= Σ xiyi + b * Σ xi + a * Σ yi + Σ 1*a*b
Σ （xi + a ）² = Σ xi² + 2 * a * Σ xi + Σ 1 * a²
Σ xi += Σ 1 * s
Σ yi += Σ 1 * t
对于修改操作，假设x修改为s+i，y修改为t+i
Σ xiyi = Σ （s+i）（t+i）= Σ 1 * s * t + Σ s * i + Σ t * i + Σ 1 * i² = Σ 1 * s * t + （s+t）* Σ i + Σ 1 * i²
同理，Σ xi² = Σ 1 * s *s + s * 2 * Σ i + Σ 1 * i²
Σ xi = Σ 1 * s +Σ i
Σ yi = Σ 1 * t +Σ i
所以 线段树还需要维护 Σi ，Σ i²
然后就是增加标记与修改标记的同时维护
可参考codevs 线段树练习5 http://www.cnblogs.com/TheRoadToTheGold/p/6690565.html
#include<cstdio>
#define N 100001
using namespace std;
int n,m,opl,opr;
double totx,toty,totxy,totxx;
double px,py,ans,fz,fm;
double x[N],y[N],s,t;
struct node
{
int l,r,siz;
double sumx,sumy,fx,fy,xx,xy;
double tagx,tagy;
bool v;
double toti,toti2;
}tr[N*];
void up(int k)
{
tr[k].sumx=tr[k<<].sumx+tr[k<<|].sumx;
tr[k].sumy=tr[k<<].sumy+tr[k<<|].sumy;
tr[k].xx=tr[k<<].xx+tr[k<<|].xx;
tr[k].xy=tr[k<<].xy+tr[k<<|].xy;
tr[k].toti=tr[k<<].toti+tr[k<<|].toti;
tr[k].toti2=tr[k<<].toti2+tr[k<<|].toti2;
}
void down(int k)
{
tr[k<<].xy+=tr[k].fy*tr[k<<].sumx+tr[k].fx*tr[k<<].sumy+tr[k].fx*tr[k].fy*tr[k<<].siz;
tr[k<<|].xy+=tr[k].fy*tr[k<<|].sumx+tr[k].fx*tr[k<<|].sumy+tr[k].fx*tr[k].fy*tr[k<<|].siz;
tr[k<<].xx+=tr[k].fx*tr[k<<].sumx+tr[k].fx*tr[k<<].sumx+tr[k].fx*tr[k].fx*tr[k<<].siz;
tr[k<<|].xx+=tr[k].fx*tr[k<<|].sumx+tr[k].fx*tr[k<<|].sumx+tr[k].fx*tr[k].fx*tr[k<<|].siz;
tr[k<<].sumx+=tr[k<<].siz*tr[k].fx;
tr[k<<].sumy+=tr[k<<].siz*tr[k].fy;
tr[k<<|].sumx+=tr[k<<|].siz*tr[k].fx;
tr[k<<|].sumy+=tr[k<<|].siz*tr[k].fy;
tr[k<<].fx+=tr[k].fx;
tr[k<<].fy+=tr[k].fy;
tr[k<<|].fx+=tr[k].fx;
tr[k<<|].fy+=tr[k].fy;
tr[k].fx=tr[k].fy=;
}
void down2(int k)
{
tr[k<<].sumx=tr[k].tagx*tr[k<<].siz+tr[k<<].toti;
tr[k<<|].sumx=tr[k].tagx*tr[k<<|].siz+tr[k<<|].toti;
tr[k<<].sumy=tr[k].tagy*tr[k<<].siz+tr[k<<].toti;
tr[k<<|].sumy=tr[k].tagy*tr[k<<|].siz+tr[k<<|].toti;
tr[k<<].xy=tr[k].tagx*tr[k].tagy*tr[k<<].siz+tr[k<<].toti*(tr[k].tagx+tr[k].tagy)+tr[k<<].toti2;
tr[k<<|].xy=tr[k].tagx*tr[k].tagy*tr[k<<|].siz+tr[k<<|].toti*(tr[k].tagx+tr[k].tagy)+tr[k<<|].toti2;
tr[k<<].xx=tr[k].tagx*tr[k].tagx*tr[k<<].siz+tr[k<<].toti*tr[k].tagx*+tr[k<<].toti2;
tr[k<<|].xx=tr[k].tagx*tr[k].tagx*tr[k<<|].siz+tr[k<<|].toti*tr[k].tagx*+tr[k<<|].toti2;
tr[k<<].tagx=tr[k].tagx;
tr[k<<|].tagx=tr[k].tagx;
tr[k<<].tagy=tr[k].tagy;
tr[k<<|].tagy=tr[k].tagy;
tr[k<<].v=tr[k<<|].v=true;
tr[k].tagx=tr[k].tagy=tr[k].v=;
tr[k<<].fx=tr[k<<].fy=;
tr[k<<|].fx=tr[k<<|].fy=;
}
void build(int k,int l,int r)
{
tr[k].l=l; tr[k].r=r; tr[k].siz=r-l+;
if(l==r)
{
tr[k].sumx=x[l];
tr[k].sumy=y[l];
tr[k].xx=x[l]*x[l];
tr[k].xy=x[l]*y[l];
tr[k].toti=l;
tr[k].toti2=(double)l*l;
return;
}
int mid=l+r>>;
build(k<<,l,mid);
build(k<<|,mid+,r);
up(k);
}
void query(int k)
{
if(tr[k].l>=opl&&tr[k].r<=opr)
{
totx+=tr[k].sumx;
toty+=tr[k].sumy;
totxy+=tr[k].xy;
totxx+=tr[k].xx;
return;
}
if(tr[k].v) down2(k);
if(tr[k].fx||tr[k].fy) down(k);
int mid=tr[k].l+tr[k].r>>;
if(opl<=mid) query(k<<);
if(opr>mid) query(k<<|);
}
void add(int k)
{
if(tr[k].l>=opl&&tr[k].r<=opr)
{
tr[k].xy+=t*tr[k].sumx+s*tr[k].sumy+s*t*tr[k].siz;
tr[k].xx+=s*tr[k].sumx+s*tr[k].sumx+s*s*tr[k].siz;
tr[k].sumx+=s*tr[k].siz;
tr[k].sumy+=t*tr[k].siz;
tr[k].fx+=s;
tr[k].fy+=t;
return;
}
if(tr[k].v) down2(k);
if(tr[k].fx||tr[k].fy) down(k);
int mid=tr[k].l+tr[k].r>>;
if(opl<=mid) add(k<<);
if(opr>mid) add(k<<|);
up(k);
}
void change2(int k)
{
if(tr[k].l>=opl&&tr[k].r<=opr)
{
tr[k].fx=tr[k].fy=;
tr[k].tagx=s;tr[k].tagy=t;
tr[k].v=true;
tr[k].sumx=s*tr[k].siz+tr[k].toti;
tr[k].sumy=t*tr[k].siz+tr[k].toti;
tr[k].xy=s*t*tr[k].siz+tr[k].toti*(s+t)+tr[k].toti2;
tr[k].xx=s*s*tr[k].siz+tr[k].toti*s*+tr[k].toti2;
return;
}
if(tr[k].v) down2(k);
if(tr[k].fx||tr[k].fy) down(k);
int mid=tr[k].l+tr[k].r>>;
if(opl<=mid) change2(k<<);
if(opr>mid) change2(k<<|);
up(k);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++) scanf("%lf",&x[i]);
for(int i=;i<=n;i++) scanf("%lf",&y[i]);
build(,,n);
int z,u;
while(m--)
{
scanf("%d",&z);
if(z==)
{
scanf("%d%d",&opl,&opr);
u=opr-opl+;
totx=; toty=; totxy=; totxx=;
query();
px=totx/u;
py=toty/u;
fz=totxy-totx*py-px*toty+px*py*u;
fm=totxx-totx*px*+px*px*u;
ans=fz/fm;
printf("%.10lf\n",ans);
}
else if(z==)
{
scanf("%d%d",&opl,&opr);
scanf("%lf%lf",&s,&t);
add();
}
else
{
scanf("%d%d",&opl,&opr);
scanf("%lf%lf",&s,&t);
change2();
}
}
return ;
}