树状数组入门,对这种被动接受的东西,总是不习惯
code
#include <set> #include <map> #include <ctime> #include <queue> #include <cmath> #include <stack> #include <limits> #include <vector> #include <bitset> #include <string> #include <cstdio> #include <cstring> #include <fstream> #include <string.h> #include <iostream> #include <algorithm> #define ls rt<<1 #define rs rt<<1|1 #define Si set<int> #define LL long long #define pb push_back #define PS printf(" ") #define Vi vector<int> #define LN printf("\n") #define SD(a) scanf("%d",&a) #define PD(a) printf("%d",a) #define SET(a,b) memset(a,b,sizeof(a)) #define FF(i,a) for(int i(0);i<(a);i++) #define FD(i,a) for(int i(a);i>=(1);i--) #define FOR(i,a,b) for(int i(a);i<=(b);i++) #define FOD(i,a,b) for(int i(a);i>=(b);i--) #define readf freopen("input.txt","r",stdin) #define writef freopen("output.txt","w",stdout) const int maxn = 10000005; const int INF = 0x3fffffff; const int dx[]={0,1,0,-1}; const int dy[]={1,0,-1,0}; const double pi = acos(-1.0); using namespace std; //素数筛法 bool prime[maxn]; void IsPrime(){ prime[0]=prime[1]=0;prime[2]=1; for(int i=3;i<maxn;i=i+2) prime[i]=1; int t=(int)sqrt(maxn*1.0); for(int i=3;i<=t;i++) if(prime[i]) for(int j=i*i;j<maxn;j+=2*i)//优化 prime[j]=0; } int C,N,M; int a[1000001]; int c[1000001]; int lowbit(int t){ return t&(-t); } void add(int pos,int v){ while(pos<=C){ c[pos]+=v; pos+=lowbit(pos); } } int sum(int n){ int sum=0; while(n>0){ sum+=c[n]; n-=lowbit(n); } return sum; } int main() { IsPrime(); int cas=1; while(~scanf("%d%d%d",&C,&N,&M)&&(C+N+M)){ SET(c,0); bool t=prime[M]; FOR(i,1,C){ if(t) add(i,1); a[i]=M; } printf("CASE #%d:\n",cas++); int k,b,c; FOR(i,1,N){ scanf("%d%d%d",&k,&b,&c); if(k==0){ if(prime[a[b]]){ a[b]+=c; if(!prime[a[b]]) add(b,-1); }else{ a[b]+=c; if(prime[a[b]]) add(b,1); } }else printf("%d\n",sum(c)-sum(b-1)); } LN; } return 0; }