P2122 还教室

· · 题解

这道题一看，就是线段树。

分析三种操作：

①第 l 天到第 r 天，每天被归还 d 个教室。

所属类型：区间加。

②询问第 l 天到第 r 天教室个数的平均数。

所属类型：区间和。

③询问第 l 天到第 r 天教室个数的方差。

这个有些特别，首先我们说一下什么是方差：

平均数定义：\bar{a}=\dfrac{1}{n}\sum\limits_{i=1}^{n}a_i

方差定义：s^2=\dfrac{1}{n}\sum\limits_{i=1}^n(a_i-\bar{a})

简化后得：s^2=\dfrac{1}{n^2}(n\sum\limits_{i=1}^n{a_i}^2-(\sum\limits_{i=1}^na_i)^2)

简化过程参见：https://www.luogu.com.cn/blog/yuruochen/noip2021-fang-ci-ti-xie

现在问题就很简单了。

所属类型：区间和、区间平方和。

但是我们如何在区间加时更新区间平方和呢？

我们知道，对于每个 a_i，都有：(a_i+k)^2-a_i^2=a_i^2+2a_ik+k^2-a_i^2=2a_ik+k^2

因此，我们将平方和 sqsum_{l,r} 加上 2\times sum_{l,r}\times k+(r-l+1)\times k^2 就可以了！

一个坑点：

要开 long long！

剩下的直接套用模板就 OK 了：

#include<bits/stdc++.h>
#define N 100005
#define int long long
using namespace std;
int n,m,sum[N<<2],sqsum[N<<2],add[N<<2];
void push_down(int rt,int m){
    if(add[rt]){
        add[rt<<1]+=add[rt];
        add[rt<<1|1]+=add[rt];
        sqsum[rt<<1]+=2*sum[rt<<1]*add[rt]+add[rt]*add[rt]*(m-(m>>1));
        sqsum[rt<<1|1]+=2*sum[rt<<1|1]*add[rt]+add[rt]*add[rt]*(m>>1);
        sum[rt<<1]+=add[rt]*(m-(m>>1));
        sum[rt<<1|1]+=add[rt]*(m>>1);
        add[rt]=0;
    }
}
void push_up(int rt){
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
    sqsum[rt]=sqsum[rt<<1]+sqsum[rt<<1|1];
}
void build(int l,int r,int rt){
    if(l==r){
        scanf("%lld",&sum[rt]);sqsum[rt]=sum[rt]*sum[rt];
        return;
    }
    int mid=l+r>>1;
    build(l,mid,rt<<1);
    build(mid+1,r,rt<<1|1);
    push_up(rt);
}
void update(int l,int r,int rt,int a,int b,int c){
    if(a<=l&&b>=r){
        add[rt]+=c;
        sqsum[rt]+=2*sum[rt]*c+c*c*(r-l+1);
        sum[rt]+=c*(r-l+1);
        return;
    }
    push_down(rt,r-l+1);
    int mid=l+r>>1;
    if(a<=mid) update(l,mid,rt<<1,a,b,c);
    if(b>mid) update(mid+1,r,rt<<1|1,a,b,c);
    push_up(rt);
}
int query_sqsum(int l,int r,int rt,int a,int b){
    if(a<=l&&b>=r) return sqsum[rt];
    push_down(rt,r-l+1);
    int mid=l+r>>1,ans=0;
    if(a<=mid) ans+=query_sqsum(l,mid,rt<<1,a,b);
    if(b>mid) ans+=query_sqsum(mid+1,r,rt<<1|1,a,b);
    return ans;
}
int query_sum(int l,int r,int rt,int a,int b){
    if(a<=l&&b>=r) return sum[rt];
    push_down(rt,r-l+1);
    int mid=l+r>>1,ans=0;
    if(a<=mid) ans+=query_sum(l,mid,rt<<1,a,b);
    if(b>mid) ans+=query_sum(mid+1,r,rt<<1|1,a,b);
    return ans;
}
void print_division(int a,int b){
    if(!a) printf("0/1");
    else printf("%lld/%lld",a/__gcd(a,b),b/__gcd(a,b));
}
signed main(){
    scanf("%lld%lld",&n,&m);
    build(1,n,1);
    while(m--){
        int op,l,r,d;scanf("%lld%lld%lld",&op,&l,&r);
        if(op==1) scanf("%lld",&d),update(1,n,1,l,r,d);
        else if(op==2) print_division(query_sum(1,n,1,l,r),r-l+1),putchar(10);
        else{
            int s1=query_sqsum(1,n,1,l,r),s2=query_sum(1,n,1,l,r);
            print_division((r-l+1)*s1-s2*s2,(r-l+1)*(r-l+1)),putchar(10);
        }
    }
    return 0;
}