洛谷P5142 区间方差 题解

题目链接：P5142 区间方差

题意：

对于一个长度为 $n$ 的序列 $a_1,a_2,a_3\cdots a_n$，我们定义它的平均数 $a$ 为:

$$a=\frac{1}{n}\sum _{i=1}^n{a}_i$$

并定义它的方差 $d$ 为:

$$d=\frac{1}{n}\sum _{i=1}^n(a_i-a{)}^2$$
现在给定一个长度为 $n$ 的序列 $a_1,a_2\cdots a_n$。你需要支持两种操作。每种操作的格式为 c x y。

若 $c=1$，为修改操作，代表将 $a_x$ 赋值为 $y$。

若 $c=2$，为查询操作，代表查询 $a_x$ 到 $a_y$ 的方差。

为了避免浮点数误差，请以分数取模形式输出结果（对 1000000007（$10^9+7$）取模）。

对于 $100\%$ 的数据，$1\le n,m\le 1\times 10^5$，$1\le a_i\le 1\times 10^9$，$1\le x\le n$。对于操作 1，$1\le y\le 1\times 10^9$。对于操作2，$x\le y\le n$。

方差有个更快的公式
$$\frac{{\sum }_{i=1}^n{a}_i^2}{n}-a^2$$
推导过程很简单，只要把那个 $(a-a_i{)}^2$ 展开就好了

这样我们就只要维护两个数组
S 1 = ∑ i = l r a i S 2 = ∑ i = l r a i 2

S1​S2​​=i=l∑r​ai​=i=l∑r​ai2​​
单点修改都不需要懒标记，很水吧

不过这个取模除法，所以要算个逆元

因为 $10^9+7$ 是个质数，而且 $a_i\le 10^9$

所以直接用费马小定理那个东西求个逆元就好了

时间复杂度 $O(m\log (n{a}_i))$

代码：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
namespace FastIO
{
    #define gc() readchar()
    #define pc(a) putchar(a)
    #define SIZ (int)(1e6+15)
    char buf1[SIZ],*p1,*p2;
    char readchar()
    {
        if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
        return p1==p2?EOF:*p1++;
    }
    template<typename T>void read(T &k)
    {
        char ch=gc();T x=0,f=1;
        while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
        while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
        k=x*f;
    }
    template<typename T>void write(T k)
    {
        if(k<0){k=-k;pc('-');}
        static T stk[66];T top=0;
        do{stk[top++]=k%10,k/=10;}while(k);
        while(top){pc(stk[--top]+'0');}
    }
}using namespace FastIO;
#define N (int)(1e5+15)

const int p=1e9+7;
int n,Q,a[N],sum1[N<<2],sum2[N<<2];
#define ls(x) ((x)<<1)
#define rs(x) ((x)<<1|1)
int qpow(int a,int b)
{
    int ans=1,base=a%p;
    while(b)
    {
        if(b&1) ans=ans*base%p;
        base=base*base%p;
        b>>=1;
    }
    return ans;
}
int inv(int x){return qpow(x,p-2);}
void push_up(int at)
{
    sum1[at]=(sum1[ls(at)]+sum1[rs(at)])%p;
    sum2[at]=(sum2[ls(at)]+sum2[rs(at)])%p;
}
void build(int l,int r,int at)
{
    if(l==r)
    {
        sum1[at]=a[l]%p;
        sum2[at]=a[l]%p*a[l]%p;
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,ls(at));
    build(mid+1,r,rs(at));
    push_up(at);
}
void modify(int x,int l,int r,int k,int at)
{
    if(l==r)
    {
        sum1[at]=k%p;
        sum2[at]=k%p*k%p;
        return;
    }
    int mid=(l+r)>>1;
    if(x<=mid)modify(x,l,mid,k,ls(at));
    else modify(x,mid+1,r,k,rs(at));
    push_up(at);
}
int query1(int nl,int nr,int l,int r,int at)
{
    if(nl<=l&&r<=nr) return sum1[at]%p;
    int mid=(l+r)>>1;
    int res=0;
    if(nl<=mid) res=(res+query1(nl,nr,l,mid,ls(at)))%p;
    if(nr>mid) res=(res+query1(nl,nr,mid+1,r,rs(at)))%p;
    return res;
}
int query2(int nl,int nr,int l,int r,int at)
{
    if(nl<=l&&r<=nr) return sum2[at]%p;
    int mid=(l+r)>>1;
    int res=0;
    if(nl<=mid) res=(res+query2(nl,nr,l,mid,ls(at)))%p;
    if(nr>mid) res=(res+query2(nl,nr,mid+1,r,rs(at)))%p;
    return res;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    read(n);read(Q);
    for(int i=1; i<=n; i++)
        read(a[i]);
    build(1,n,1);
    for(int op,x,y; Q--; )
    {
        read(op); read(x); read(y);
        if(op==1) modify(x,1,n,y,1);
        else
        {
            int t1=query2(x,y,1,n,1);
            int t2=query1(x,y,1,n,1);
            int t3=inv(y-x+1);
            t1=t1%p*t3%p;
            t2=t2%p*t3%p;t2=t2%p*t2%p;
            write(((t1-t2)%p+p)%p);pc('\n');
        }
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132