P6180 【[USACO15DEC]Breed Counting S】

原题链接

题意简述

给出 $n$ 头奶牛,每头可分为三种,对于 $q$ 次询问,给出区间内各种奶牛的数量。

思路

题目的数据范围限制为 $N,Q\leq10^5$ ,肯定不能够使用暴力对于每一个区间跑一遍统计。这一题有只要求查询而不要求修改,很自然就想到了前缀和。

前缀和

那么什么是前缀和呢?

根据OI Wiki 上的解释

前缀和是一种重要的预处理,能大大降低查询的时间复杂度。我们可以简单理解为“数列的前 $n$ 项的和”。

如果用数组 $a$ 和其前缀和数组 $b$ 表示出来

$a_1=1,a_2=5,a_3=3,a_4=2,…$

则数组 $b$

$b_1=1,b_2=6,b_3=9,b_4=11,…$

不难推出式子

如果要查询数组 $a$ 从 $l$ 到 $r$ 之间所有数的和,只用输出 $br-b{l-1}$​ ,

原理:

注意,一定是 $l-1$ 如果是 $l$ 就会将 $a_l$ 减去

根据上述,给出代码如下

代码

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
#include <bits/stdc++.h>
using namespace std;
inline int read() {
char ch = getchar();
int ret = 0, f = 1;
while (ch < '0' || ch > '9') {
if (ch == '-')
f = -f;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
ret = (ret << 1) + (ret << 3) + ch - '0';
ch = getchar();
}
return ret * f;
}
const int N = 100005;
int n, q, a[2][N], b[2][N], c[2][N];
// a[0],b[0],c[0]为原始数组
// a[1],b[1],c[1]为对应的前缀和数组
int main() {
n = read();
q = read();
for (int i = 1; i <= n; i++) {
int t = read();
if (t == 1)
a[0][i]++;
else if (t == 2)
b[0][i]++;
else if (t == 3)
c[0][i]++;
a[1][i] = a[1][i - 1] + a[0][i];
b[1][i] = b[1][i - 1] + b[0][i];
c[1][i] = c[1][i - 1] + c[0][i];
}
for (int i = 1; i <= q; i++) {
int l = read(), r = read();
printf("%d %d %d\n", a[1][r] - a[1][l - 1], b[1][r] - b[1][l - 1], c[1][r] - c[1][l - 1]);
}
}

后记

前缀和的应用并不只上述这么简单,许多看似基础的算法也是如此,往往可以通过一些有趣的改进拓展到更多地方。

文章作者: answerend42
文章链接: http://answerend42.github.io/2020/03/08/lg6180/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 answerend42的Blog