洛谷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的序列$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$ 代入继续变形

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

注意到之前设的 $F$ 和 $G$ 是

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


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

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

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

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《方差》