`
Simone_chou
  • 浏览: 182788 次
  • 性别: Icon_minigender_2
  • 来自: 广州
社区版块
存档分类
最新评论

经理的烦恼(树状数组 + 素数)

    博客分类:
  • HOJ
 
阅读更多

经理的烦恼

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

 

 

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics