洛谷P5142《区间方差》

十月 26, 2019 6169

简单的数据结构题目以及无处不在的取模

题目背景

出题人并没有能力写有趣的题面……

题目描述

对于一个长度为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的序列 b_1,b_2\cdots b_n ​。你需要支持两种操作。每种操作的格式为c x y。

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

若c=2，为查询操作，代表查询 b_x ​到 b_y 的方差。

为了避免浮点数误差，请以分数取模形式输出结果（对1000000007（ 10^9+7 ）取模）。如果不知道什么是分数取模，请看下文。

作者注：原文这里是对乘法逆元对介绍，在此省略

输入格式

第一行两个数n,m，代表序列b的长度为n，有m个操作。

第二行n个整数 b_i ​，表示序列b的初始值。

下面有m行整数，每行格式为c a b，含义如上文所示。保证所有操作合法。

输出格式

对于每个操作2，输出一行。

输入输出样例

输入 #1

1
2
3
4
5
6
7
8
9
10
4 8
0 0 0 0
1 1 1
1 2 2
1 3 3
1 4 4
2 1 1
2 1 2
2 1 3
2 1 4

输出 #1

1
2
3
4
0
250000002
666666672
250000003

说明/提示

四次修改后，序列b为：1,2,3,4。

区间[1,1]的方差为0.

区间[1,2]的方差为1/4。4的逆元为250000002。

区间[1,3]的方差为2/3。3的逆元为333333336，2*333333336%M=666666672。

对于50%的数据，n≤1000，m≤1000.

对于100%的数据，n≤100000，m≤100000，1≤b_i≤1000000000，1≤x≤n。对于操作1，1≤y≤1000000000。对于操作2，x≤y≤n。

保证逆元一定存在。注意M=1000000007（10^9+7）。

解析

没啥可解析的……推推式子就完了

查询 [l,r] 的方差：
首先令 N = r - l + 1 ，有

a = {1 \over N} \sum_{i = l}^{r} a_i

而且

d = {1 \over N} \sum_{i = l}^{r} (a_i - a)^2

对下面的式子作一番变形：

\begin{align*} d &= {1 \over N} \sum_{i = l}^{r} (a_i - a)^2 \\&= {1 \over N} \sum_{i = l}^{r} (a_i^2 + a^2 - 2 a \cdot a_i) \\&= {1 \over N} \big( \sum_{i = l}^{r} a_i^2 + \sum_{i = l}^{r} a^2 - \sum_{i = l}^{r} 2 a \cdot a_i \big) \\&= {1\over N} \big(\sum_{i = l}^{r} a_i^2 + N \times a^2 - 2a \sum_{i = l}^{r} a_i\big) \\&={1\over N}\sum_{i = l}^{r} a_i^2 + {1\over N} \times N \times a^2 - {1\over N} \times2a \sum_{i = l}^{r} a_i \\&={1\over N}\sum_{i = l}^{r} a_i^2 + a^2 - {1\over N} \times2a \sum_{i = l}^{r} a_i \end{align*}

这个式子复杂的令人自闭。。
这时设

F = \sum_{i = l}^{r} a_i, G = \sum_{i = l}^{r} a_i^2

这样到后面式子会好看许多，把 a 代入继续变形

\begin{align*} d &= {1\over N}\sum_{i = l}^{r} a_i^2 + a^2 - {1\over N} \times2a \sum_{i = l}^{r} a_i \\&= {1\over N}\cdot G + {\big({1 \over N} \sum_{i = l}^{r} a_i\big)}^2 - 2 \times {1 \over N} \times {1 \over N} \sum_{i = l}^{r} a_i \times \sum_{i = l}^{r} a_i \\&= {1\over N} \cdot G + {1\over N^2} \cdot F^2-2\times {1\over N^2}\cdot F^2 \\&= {1\over N} \cdot G -{1\over N^2}\cdot F^2 \end{align*}

这个就是最后的方差式子。。。终于推出来了

注意到之前设的 F 和 G 是
MATHJAX-SSR-1578

发现这个东西似乎可以用数据结构维护

然后就是一道树状数组模板题了

维护两个树状数组，一个记录区间和，一个记录区间平方和

这个很好做吧，下面放代码

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
// 前缀和
lli qu(int p) {  
    lli r = 0;  
    while (p >= 1) {  
        (r += bit[p]) %= HA;  
        lb(p, -1ll);  
    }  
    return r;  
}  
// 前缀平方和
lli qux(int p) {  
    lli r = 0;  
    while (p >= 1) {  
        (r += bitt[p]) %= HA;  
        lb(p, -1ll);  
    }  
    return r;  
}  
// 修改，注意操作是单点覆盖而不是单点加
void mo(int p, lli x) {  
    lli d = x - (qu(p) - qu(p - 1)),  
            dx = x * x - (qux(p) - qux(p - 1));  
    while (p <= n) {  
        bit[p] = (bit[p] + d) % HA;  
        bitt[p] = (bitt[p] + dx) % HA;  
        lb(p, 1ll);  
    }  
}

然后这道省选/NOI-的题目就做完了
真就评分虚高嗷

注意几个坑点

  1. 题目的操作是单点覆盖，但是树状数组只能区间加，要先查询一下当前点的值然后加上差值，这个见代码吧
  2. 取模！取模！取模 修改和查询都要取模！还要注意负数取模的问题！

代码实现

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
//
// Created by HandwerSTD on 2019/10/23.
// Copyright (c) 2019 HandwerSTD. All rights reserved.
// Title: 区间方差
//
// sto Qingyu orz
// 感谢真神sqy无私的教诲。膜时队者处处阿克，只因大师sqy在他背后。不膜大师者违背了真神的旨意，真神必将降下天谴，
// 使其天天爆零
// 我不由自主地膜拜真神sqy。
//

#include <cstdio>

#define rap(a,s,t,i) for (int a = s; a <= t; a += i)
#define lb(x,y) ((x = x + y * (x & (-x))))

typedef long long int lli;

int getint() { int x; scanf("%d", &x); return x; }

const int MAXN = 100000 + 10;
const lli HA = 1000000007;

int n, m;
lli bit[MAXN], bitt[MAXN];

lli qu(int p) { lli r = 0; while (p >= 1) { (r += bit[p]) %= HA; lb(p, -1ll); } return r; }
lli qux(int p) { lli r = 0; while (p >= 1) { (r += bitt[p]) %= HA; lb(p, -1ll); } return r; }
void mo(int p, lli x) {
    lli d = x - (qu(p) - qu(p - 1)), dx = x * x - (qux(p) - qux(p - 1));
    while (p <= n) { bit[p] = (bit[p] + d) % HA; bitt[p] = (bitt[p] + dx) % HA; lb(p, 1ll); }
}
lli pw(lli a, lli b) { lli r = 1; while (b) { if (b & 1) r = r * a % HA; a = a * a % HA; b >>= 1; } return r; }
lli inv(lli a) { return pw(a, HA - 2); }

int main() {
    n = getint(); m = getint();
    rap (i, 1, n, 1) mo(i, getint());
    rap (i, 1, m, 1) {
        int c = getint(); int x = getint(); int y = getint();
        if (c == 1) mo(x, y);
        else {
            lli N = (y - x + 1); lli iN = inv(N);
            lli fx = (qu(y) - qu(x - 1) + HA) % HA, gx = (qux(y) - qux(x - 1) + HA) % HA;
            lli tx = (iN * gx % HA - iN * iN % HA * fx % HA * fx % HA); while (tx <= 0) tx += HA; tx %= HA;
            printf("%lld\n", tx % HA);
        }
    }
    return 0;
}

代码也不长啊，不就50行吗

相似题目

强化版：洛谷P1471《方差》