首页 > 代码库 > SDOI2017 相关分析
SDOI2017 相关分析
把两个式子拆开
Σ（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 100001using 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*4];void up(int k){ tr[k].sumx=tr[k<<1].sumx+tr[k<<1|1].sumx; tr[k].sumy=tr[k<<1].sumy+tr[k<<1|1].sumy; tr[k].xx=tr[k<<1].xx+tr[k<<1|1].xx; tr[k].xy=tr[k<<1].xy+tr[k<<1|1].xy; tr[k].toti=tr[k<<1].toti+tr[k<<1|1].toti; tr[k].toti2=tr[k<<1].toti2+tr[k<<1|1].toti2;}void down(int k){ tr[k<<1].xy+=tr[k].fy*tr[k<<1].sumx+tr[k].fx*tr[k<<1].sumy+tr[k].fx*tr[k].fy*tr[k<<1].siz; tr[k<<1|1].xy+=tr[k].fy*tr[k<<1|1].sumx+tr[k].fx*tr[k<<1|1].sumy+tr[k].fx*tr[k].fy*tr[k<<1|1].siz; tr[k<<1].xx+=tr[k].fx*tr[k<<1].sumx+tr[k].fx*tr[k<<1].sumx+tr[k].fx*tr[k].fx*tr[k<<1].siz; tr[k<<1|1].xx+=tr[k].fx*tr[k<<1|1].sumx+tr[k].fx*tr[k<<1|1].sumx+tr[k].fx*tr[k].fx*tr[k<<1|1].siz; tr[k<<1].sumx+=tr[k<<1].siz*tr[k].fx; tr[k<<1].sumy+=tr[k<<1].siz*tr[k].fy; tr[k<<1|1].sumx+=tr[k<<1|1].siz*tr[k].fx; tr[k<<1|1].sumy+=tr[k<<1|1].siz*tr[k].fy; tr[k<<1].fx+=tr[k].fx; tr[k<<1].fy+=tr[k].fy; tr[k<<1|1].fx+=tr[k].fx; tr[k<<1|1].fy+=tr[k].fy; tr[k].fx=tr[k].fy=0;}void down2(int k){ tr[k<<1].sumx=tr[k].tagx*tr[k<<1].siz+tr[k<<1].toti; tr[k<<1|1].sumx=tr[k].tagx*tr[k<<1|1].siz+tr[k<<1|1].toti; tr[k<<1].sumy=tr[k].tagy*tr[k<<1].siz+tr[k<<1].toti; tr[k<<1|1].sumy=tr[k].tagy*tr[k<<1|1].siz+tr[k<<1|1].toti; tr[k<<1].xy=tr[k].tagx*tr[k].tagy*tr[k<<1].siz+tr[k<<1].toti*(tr[k].tagx+tr[k].tagy)+tr[k<<1].toti2; tr[k<<1|1].xy=tr[k].tagx*tr[k].tagy*tr[k<<1|1].siz+tr[k<<1|1].toti*(tr[k].tagx+tr[k].tagy)+tr[k<<1|1].toti2; tr[k<<1].xx=tr[k].tagx*tr[k].tagx*tr[k<<1].siz+tr[k<<1].toti*tr[k].tagx*2+tr[k<<1].toti2; tr[k<<1|1].xx=tr[k].tagx*tr[k].tagx*tr[k<<1|1].siz+tr[k<<1|1].toti*tr[k].tagx*2+tr[k<<1|1].toti2; tr[k<<1].tagx=tr[k].tagx; tr[k<<1|1].tagx=tr[k].tagx; tr[k<<1].tagy=tr[k].tagy; tr[k<<1|1].tagy=tr[k].tagy; tr[k<<1].v=tr[k<<1|1].v=true; tr[k].tagx=tr[k].tagy=tr[k].v=0; tr[k<<1].fx=tr[k<<1].fy=0; tr[k<<1|1].fx=tr[k<<1|1].fy=0;}void build(int k,int l,int r){ tr[k].l=l; tr[k].r=r; tr[k].siz=r-l+1; 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>>1; build(k<<1,l,mid); build(k<<1|1,mid+1,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>>1; if(opl<=mid) query(k<<1); if(opr>mid) query(k<<1|1);}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>>1; if(opl<=mid) add(k<<1); if(opr>mid) add(k<<1|1); up(k);}void change2(int k){ if(tr[k].l>=opl&&tr[k].r<=opr) { tr[k].fx=tr[k].fy=0; 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*2+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>>1; if(opl<=mid) change2(k<<1); if(opr>mid) change2(k<<1|1); up(k);}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); int z,u; while(m--) { scanf("%d",&z); if(z==1) { scanf("%d%d",&opl,&opr); u=opr-opl+1; totx=0; toty=0; totxy=0; totxx=0; query(1); px=totx/u; py=toty/u; fz=totxy-totx*py-px*toty+px*py*u; fm=totxx-totx*px*2+px*px*u; ans=fz/fm; printf("%.10lf\n",ans); } else if(z==2) { scanf("%d%d",&opl,&opr); scanf("%lf%lf",&s,&t); add(1); } else { scanf("%d%d",&opl,&opr); scanf("%lf%lf",&s,&t); change2(1); } } return 0;}
SDOI2017 相关分析
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。