HIT 1867 经理的烦恼（树状数组）

经理的烦恼

erry是一家公司销售部门的经理。这家公司有很多连锁店，编号为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


思路：直接在树状数组中存储是素数的个数，假设现在改变了店铺x的值，那么我们可以通过判断前后是否是质数的关系来更新树状数组（具体详见代码）

代码：

#include<stdio.h>
#include<math.h>
#include<string.h>

#define maxn 1000010
int a[maxn],num[maxn];
int n,q,k;

int lowbit(int x)
{
return x&-x;
}

bool judge(int x)//判断是否为素数
{
if(x<=1)
return 0;
for(int i=2; i<=sqrt(x); ++i)
if(x%i==0)
return 0;
return 1;
}

void add(int i,int val)
{
while(i<=n)
    {
        a[i]+=val;
        i+=lowbit(i);
    }
}

int getsum(int i)
{
int sum=0;
while(i)
    {
        sum+=a[i];
        i-=lowbit(i);
    }
return sum;
}

void init()//初始化
{
    memset(a,0,sizeof(a));
int s=0;
if(judge(k))
s=1;
for(int i=1; i<=n; ++i)
        num[i]=k,add(i,s);
}

int main()
{
int T=0;
while(~scanf("%d%d%d",&n,&q,&k),n||q||k)
    {
        init();
printf("CASE #%d:\n",++T);
int op,x,y;
for(int i=0; i<q; ++i)
        {
            scanf("%d%d%d",&op,&x,&y);
if(op)
printf("%d\n",getsum(y)-getsum(x-1));
else
            {
int tmp=num[x];
                num[x]+=y;
if(judge(num[x]))
                {
if(!judge(tmp))
                        add(x,1);
                }
else
                {
if(judge(tmp))
                        add(x,-1);
                }
            }
        }
        puts("");
    }
return 0;
}

总结：写的时候隐约想到了直接存储素数的个数，但是没去深想啊，以为素数打表查询时判断一下也能过。。。还是对树状数组不够熟练啊！