总经理的烦恼(树状数组 + 素数)
经理的烦恼(树状数组 + 素数)
经理的烦恼
Source : HCPC 2005 Spring | |||
Time limit : 2 sec | Memory limit : 32 M |
Submitted : 2567, Accepted : 605
Jerry是一家公司销售部门的经理。这家公司有很多连锁店,编号为1,2,3,... Jerry每天必须关注每家连锁店的商品数量及其变化,一项很乏味的工作。在连锁店比较少的时候,Jerry喜欢计算编号在[i,j]区间内的连锁店中商品数量为素数的有多少家,但是现在连锁店的数量急剧增长,计算量很大,Jerry很难得出结果。
输入格式
题目有多组输入。每组输入第一行有三个整数:C 连锁店的数量 N 指令的条数 M 每家连锁店初始的商品数量
接下来有N行,每行有一条指令。指令的格式为:
0 x y 连锁店x的商品数量变化值为y,y > 0商品数量增加, y < 0减少
1 i j 输出编号在[i,j]区间内的连锁店中商品数量为素数的有多少家
1 <= i, x, j < 1000000 连锁店中的商品数量a满足 0 <= a < 10000000,C = N = M = 0标志输入结束
输出格式
对于每组输入,输出它的序号。对于一组输入中的1指令输出要求的整数。每组输出后打印一行空行。
样例输入
100000 4 4 0 1 1 1 4 10 0 11 3 1 1 11 20 3 0 1 1 20 0 3 3 1 1 20 0 0 0样例输出
CASE #1: 0 2 CASE #2: 0 1
思路:
树状数组。开两个数组,一个是树状数组 bit 维护每个店是否为素数的 0,1 情况;还有另外一个数组保存每个店的商品数量信息,每次更新的时候判断是否从素数变成合数,或者从合数变成素数,询问总数则树状数组求和即可。 处理素数直接判断就好,如果开素数表的话会 MLE。
AC:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int MAX = 1000005; int shop[MAX], bit[MAX]; int c, n, m; bool pri(int num) { if (num == 1 || !num) return false; for (int i = 2; i * i <= num; ++i) if (!(num % i)) return false; return true; } int sum(int i) { int s = 0; while (i > 0) { s += bit[i]; i -= i & -i; } return s; } void add(int i, int x) { while (i <= c) { bit[i] += x; i += i & -i; } } int main() { int T = 0; while (~scanf("%d%d%d", &c, &n, &m) && (c + n + m)) { ++T; int tt = 0; memset(bit, 0, sizeof(bit)); int temp = pri(m) ? 1 : 0; for (int i = 1; i <= c; ++i) { if (temp) add(i, 1); shop[i] = m; } printf("CASE #%d:\n", T); while (n--) { int w, a, b; scanf("%d%d%d", &w, &a, &b); if (w) { printf("%d\n", sum(b) - sum(a - 1)); } else { int last = sum(a) - sum(a - 1); shop[a] += b; if (last && !pri( shop[a] )) add(a, -1); if (!last && pri( shop[a] )) add(a, 1); } } printf("\n"); } return 0; }