2 条题解
-
0
搬运工 (syrth0p1) LV 10 @ 2025-06-09 20:11:28
#include<bits/stdc++.h> using namespace std; typedef int ll; typedef long long int li; typedef long double db; const ll MAXN=2e5+51; struct SegmentTree{ ll l,r,tag; db sxx,sxy,sx,sy,tagx,tagy; }; SegmentTree tree[MAXN<<2]; ll n,qcnt,op,l,r,len; SegmentTree p,g; db s,t; db x[MAXN],y[MAXN]; inline ll read() { register ll num=0,neg=1; register char ch=getchar(); while(!isdigit(ch)&&ch!='-') { ch=getchar(); } if(ch=='-') { neg=-1; ch=getchar(); } while(isdigit(ch)) { num=(num<<3)+(num<<1)+(ch-'0'); ch=getchar(); } return num*neg; } inline db sum2(ll x) { return 1.0*x*(x+1)*(2*x+1)/6; } #define ls node<<1 #define rs (node<<1)|1 inline void update(ll node) { tree[node].sxx=tree[ls].sxx+tree[rs].sxx; tree[node].sxy=tree[ls].sxy+tree[rs].sxy; tree[node].sx=tree[ls].sx+tree[rs].sx; tree[node].sy=tree[ls].sy+tree[rs].sy; } inline void create(ll l,ll r,ll node) { tree[node]=(SegmentTree){l,r}; if(l==r) { tree[node].sx=x[l],tree[node].sy=y[l]; return (void)(tree[node].sxx=x[l]*x[l],tree[node].sxy=x[l]*y[l]); } ll mid=(tree[node].l+tree[node].r)>>1; create(l,mid,ls),create(mid+1,r,rs),update(node); } inline void spread(ll node) { ll lenl=tree[ls].r-tree[ls].l+1,lenr=tree[rs].r-tree[rs].l+1; if(tree[node].tag) { tree[ls].sx=tree[ls].sy=lenl*tree[ls].l+lenl*(lenl-1)/2.0; tree[rs].sx=tree[rs].sy=lenr*tree[rs].l+lenr*(lenr-1)/2.0; tree[ls].sxx=tree[ls].sxy=sum2(tree[ls].r)-sum2(tree[ls].l-1); tree[rs].sxx=tree[rs].sxy=sum2(tree[rs].r)-sum2(tree[rs].l-1); tree[ls].tag=tree[rs].tag=1,tree[node].tag=0; tree[ls].tagx=tree[ls].tagy=tree[rs].tagx=tree[rs].tagy=0; } if(tree[node].tagx!=0||tree[node].tagy!=0) { db u=tree[node].tagx,v=tree[node].tagy; tree[ls].sxx+=2*u*tree[ls].sx+lenl*u*u; tree[rs].sxx+=2*u*tree[rs].sx+lenr*u*u; tree[ls].sxy+=u*tree[ls].sy+v*tree[ls].sx+lenl*u*v; tree[rs].sxy+=u*tree[rs].sy+v*tree[rs].sx+lenr*u*v; tree[ls].sx+=lenl*u,tree[ls].sy+=lenl*v; tree[rs].sx+=lenr*u,tree[rs].sy+=lenr*v; tree[ls].tagx+=u,tree[rs].tagx+=u,tree[node].tagx=0; tree[ls].tagy+=v,tree[rs].tagy+=v,tree[node].tagy=0; } } inline void add(ll l,ll r,db s,db t,ll node) { if(l<=tree[node].l&&r>=tree[node].r) { ll len=tree[node].r-tree[node].l+1; tree[node].sxx+=2*s*tree[node].sx+len*s*s; tree[node].sxy+=s*tree[node].sy+t*tree[node].sx+len*s*t; tree[node].sx+=len*s,tree[node].sy+=len*t; return (void)(tree[node].tagx+=s,tree[node].tagy+=t); } ll mid=(tree[node].l+tree[node].r)>>1; spread(node),l<=mid?add(l,r,s,t,ls):(void)1,r>mid?add(l,r,s,t,rs):(void)1; update(node); } inline void cover(ll l,ll r,ll node) { if(l<=tree[node].l&&r>=tree[node].r) { ll len=tree[node].r-tree[node].l+1; tree[node].sxx=tree[node].sxy=sum2(tree[node].r)-sum2(tree[node].l-1); tree[node].sx=tree[node].sy=tree[node].l*len+len*(len-1)/2.0; return (void)(tree[node].tag=1,tree[node].tagx=tree[node].tagy=0); } ll mid=(tree[node].l+tree[node].r)>>1; spread(node),l<=mid?cover(l,r,ls):(void)1,r>mid?cover(l,r,rs):(void)1; update(node); } inline SegmentTree query(ll l,ll r,ll node) { SegmentTree u=g,v=g; if(l<=tree[node].l&&r>=tree[node].r) { return tree[node]; } ll mid=(tree[node].l+tree[node].r)>>1; spread(node); l<=mid?(void)(u=query(l,r,ls)):(void)1; r>mid?(void)(v=query(l,r,rs)):(void)1; return (SegmentTree){0,0,0,u.sxx+v.sxx,u.sxy+v.sxy,u.sx+v.sx,u.sy+v.sy}; } int main() { n=read(),qcnt=read(); for(register int i=1;i<=n;i++) { scanf("%Lf",&x[i]); } for(register int i=1;i<=n;i++) { scanf("%Lf",&y[i]); } create(1,n,1); for(register int i=1;i<=qcnt;i++) { op=read(),l=read(),r=read(); if(op==1) { p=query(l,r,1),len=r-l+1; printf("%.3Lf\n",(p.sxy-p.sx*p.sy/len)/(p.sxx-p.sx*p.sx/len)); continue; } scanf("%Lf%Lf",&s,&t),op==3?cover(l,r,1):(void)1,add(l,r,s,t,1); } }
-
-12022-07-20 13:42:24@
//加油,你能做出来的。
- 1
信息
- ID
- 2018
- 难度
- 7
- 分类
- (无)
- 标签
- 递交数
- 42
- 已通过
- 7
- 通过率
- 17%
- 被复制
- 2
- 上传者