题目链接：
?id=1867
题目大意：
有C家连锁店，编号1~C，有N条指令，每家店初始的商品数目都是M。接下来N行是命令。
命令0：0 x w，连锁店x的商品数量变化为w，w > 0商品数量增加，w < 0商品数量减少。
命令1：1 x y，询问编号区间为[x，y]的连锁店商品为素数的商店有多少家。
思路：
因为区间比较大，所以用树状数组来做。用一个数组Shop[]来存放每家店的商品数目，Tree[]
表示树状数组。如果初始商品数量m是素数的话，则每家商店商品都为素数，遍历更新每家店。
对于命令0，如果该店铺x的商品数Shop[x]为素数，，先更新Updata(x，-1)，将Shop[x]先视为
这样更新后结果就正确了。对于命令1，则输出：Query(y)-Query(x-1)即可。
AC代码：
#include<iostream>#include<algorithm>#include<cstdio>#include<cstring>#include<cmath>#define LL long longusing namespace std;int Tree[1000010],Shop[1000010],N = 1000000;int Lowbit(int x){return x &(-x);}void Update(int i,int x){while(i <= N){Tree[i] += x;i += Lowbit(i);}}LL Query(int n){LL sum = 0;while(n > 0){sum += Tree[n];n -= Lowbit(n);}return sum;}bool IsPrime(int x){if(x <= 1)return 0;for(int i = 2; i <= sqrt(x*1.0); ++i)if(x % i == 0)return false;return true;}int main(){int n,m,c,kase = 0;while(~scanf("%d%d%d",&c,&n,&m) && (c||n||m)){printf("CASE #%d:\n",++kase);memset(Tree,0,sizeof(Tree));bool temp = IsPrime(m);for(int i = 1; i <= c; ++i){//if(IsPrime(m))if(temp)Update(i,1);Shop[i] = m;}int op;for(int i = 0; i < n; ++i){scanf("%d",&op);if(op == 0){int x,w;scanf("%d%d",&x,&w);if(IsPrime(Shop[x]))Update(x,-1);Shop[x] += w;if(IsPrime(Shop[x]))Update(x,1);}else{int x,y;scanf("%d%d",&x,&y);printf("%lld\n",Query(y)-Query(x-1));}}printf("\n");}return 0;}
其实你已经错过了旅行的意义。
