经理的烦恼（树状数组 + 素数）

经理的烦恼

	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;
}