40pts,AC#5-#8,求调
查看原帖
40pts,AC#5-#8,求调
358759
kuailexiaoyao666楼主2023/9/29 12:34
#include<bits/stdc++.h>
using namespace std;
struct segmenttreee{
    double tree[400010];
    double lazy[400010];
}segtree,segsqtree;
int n;
int pushdown1(int root,int a,int b){
    int m = a + ((b-a)>>1);
    if(segtree.lazy[root]){
        segtree.tree[root*2] += segtree.lazy[root]*(m-a+1);
        segtree.tree[root*2+1] += segtree.lazy[root]*(b-m);
        segtree.lazy[root*2] += segtree.lazy[root];
        segtree.lazy[root*2+1] += segtree.lazy[root];
        segtree.lazy[root] = 0;
    }
    return m;
}
void add1(int i,int j,double c,int a,int b,int root){
    if(i <= a && b <= j){
        segtree.tree[root] += (b-a+1)*c,segtree.lazy[root] += c;
        return;
    }
    int m=pushdown1(root,a,b);
    if(i <= m)add1(i,j,c,a,m,root*2);
    if(j > m)add1(i,j,c,m+1,b,root*2+1);
    segtree.tree[root]=  segtree.tree[root*2] + segtree.tree[root*2+1];
}
double sum1(int i,int j,int a,int b,int root){
    if(i <= a && b <= j)return segtree.tree[root];
    int m = pushdown1(root,a,b);
    double sum = 0;
    if(i <= m)sum += sum1(i,j,a,m,root*2);
    if(j > m)sum += sum1(i,j,m+1,b,root*2+1);
    return sum;
}
int pushdown2(int root,int a,int b){
    int m = a + ((b-a)>>1);
    if(segsqtree.lazy[root]){
        double c = segsqtree.lazy[root];
        segsqtree.tree[root*2] += 2*c*sum1(a,m,1,n,1) + c*c*(m-a+1);
        segsqtree.tree[root*2+1] += 2*c*sum1(m+1,b,1,n,1) + c*c*(b-m);
        segsqtree.lazy[root*2] += c;
        segsqtree.lazy[root*2+1] += c;
        segsqtree.lazy[root] = 0;
    }
    return m;
}
void add2(int i,int j,double c,int a,int b,int root){
    if(i <= a && b <= j){
        segsqtree.tree[root] += 2*c*sum1(a,b,1,n,1) + c*c*(b-a+1);
        segsqtree.lazy[root] += c;
        return;
    }
    int m = pushdown2(root,a,b);
    if(i <= m)add2(i,j,c,a,m,root*2);
    if(j > m)add2(i,j,c,m+1,b,root*2+1);
    segsqtree.tree[root]=  segsqtree.tree[root*2] + segsqtree.tree[root*2+1];
}
double sum2(int i,int j,int a,int b,int root){
    if(i <= a && b <= j)return segsqtree.tree[root];
    int m = pushdown2(root,a,b);
    double sum = 0;
    if(i <= m)sum += sum2(i,j,a,m,root*2);
    if(j > m)sum += sum2(i,j,m+1,b,root*2+1);
    return sum;
}
double lst[100010];
void buildtree(int s,int t,int root){
    if(s == t){
        segtree.tree[root] = lst[s];
        segsqtree.tree[root] = lst[s]*lst[s];
        return;
    }
    int m = s + ((t-s)>>1);
    buildtree(s,m,root*2);
    buildtree(m+1,t,root*2+1);
    segtree.tree[root]=  segtree.tree[root*2] + segtree.tree[root*2+1];
    segsqtree.tree[root]=  segsqtree.tree[root*2] + segsqtree.tree[root*2+1];
}
int main(){
    #ifdef LOCAL
    freopen("infile.in","r",stdin);
    freopen("outfile.out","w",stdout);
    #endif //LOCAL
    int m;
    scanf("%d%d",&n,&m);
    for(int i = 1; i <= n; i++)scanf("%lf",&lst[i]);
    buildtree(1,n,1);
    while(m--){
        int op,x,y;
        scanf("%d%d%d",&op,&x,&y);
        if(op == 1){
            double k;
            scanf("%lf",&k);
            add2(x,y,k,1,n,1);
            add1(x,y,k,1,n,1);
        }
        if(op == 2){
            printf("%.4lf\n",sum1(x,y,1,n,1)/(y-x+1));
        }
        if(op == 3){
            printf("%.4lf\n",sum2(x,y,1,n,1)/(y-x+1)-sum1(x,y,1,n,1)*sum1(x,y,1,n,1)/(y-x+1)/(y-x+1));
        }
    }
    return 0;
}

2023/9/29 12:34
加载中...