簡單樹狀數組;
模板,,
題目大意,給定N個商店,有初始商品數量.有兩種指令,0 x y 表示x位置的商店的商品數量增加y
1 x y 表示查詢[x,y]區間內的商品數量為素數的商店的數目..
這裡更新的條件就變成去判斷更新值是否從非素數變成素數或是從素數變成非素數..
然後對樹狀數組進行更新..
#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;
int tree[1000010];
bool vis[1000010];
int num[1000010],a;
int qq(int c)
{
if(c<=1) return 0;
for(int i=2;i*i<=c;i++)
{
if(c%i==0)
return 0;
}
return 1;
}
int Lowbit(int i)
{
return i&(-i);
}
int show(int x)
{
int sum=0;
while(x>0)
{
sum+=tree[x];
x-=Lowbit(x);
}
return sum;
}
void yy(int x)
{
if(qq(num[x]))
{
if(!vis[x])
{
vis[x]=1;
while(x<=a)
{
tree[x]++;
x+=Lowbit(x);
}
}
}
else
{
if(vis[x])
{
vis[x]=0;
while(x<=a)
{
tree[x]--;
x+=Lowbit(x);
}
}
}
}
int main()
{
int b,c;
int t=0;
int q,w,e;
while(scanf("%d %d %d",&a,&b,&c))
{
t++;
if(a==0&&b==0&&c==0)
break;
printf("CASE #%d:\n",t);
for(int i=1;i<=a;i++)
num[i]=c;
if(qq(c))
{
for(int i=1;i<=a;i++)
{
vis[i]=1;
tree[i]=Lowbit(i);
}
}
else
{
memset(tree,0,sizeof(tree));
memset(vis,0,sizeof(vis));
}
for(int i=1;i<=b;i++)
{
scanf("%d%d%d",&q,&w,&e);
if(q==1)
{
printf("%d\n",show(e)-show(w-1));
}
else
{
num[w]+=e;
yy(w);
}
}
printf("\n");
}
return 0;
}