题解

2 条题解

  • 0
    @ 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);
        }
    }
    
  • -1
    @ 2022-07-20 13:42:24
    //加油,你能做出来的。
    
  • 1

信息

ID
2018
难度
7
分类
(无)
标签
递交数
42
已通过
7
通过率
17%
被复制
2
上传者