Hoj 1867 经理的烦恼（树状数组） - c++编程基础

TOP

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

2015-11-21 01:05:05 来源: 作者: 【大中小】浏览:3次

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指令输出要求的整数。每组输出后打印一行空行。

样例输入

样例输出

CASE #1:
0
2

CASE #2:
0
1

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           #include
          
            #include
            #define L(x) (x<<1) #define R(x) (x<<1|1) #define MID(x,y) ((x+y)>>1) #define eps 1e-8 typedef long long ll; #define fre(i,a,b) for(i = a; i 
            
             = a;i--) #define mem(t, v) memset ((t) , v, sizeof(t)) #define ssf(n) scanf(%s, n) #define sf(n) scanf(%d, &n) #define sff(a,b) scanf(%d %d, &a, &b) #define sfff(a,b,c) scanf(%d %d %d, &a, &b, &c) #define pf printf #define bug pf(Hi ) using namespace std; #define INF 0x3f3f3f3f #define N 1000005 ll a[N],c[N]; int n,m; int judge(int x) { if(x==0) return 0; if(x==1) return 0; if(x==2) return 1; for(int i=2;i<=(int)sqrt(x)+1;i++) if(x%i==0) return 0; return 1; } inline int lowbit(int x) { return x&(-x); } void update(int x,int va) { while(x<=n) { c[x]+=va; x+=lowbit(x); } } int sum(int x) { int s=0; while(x) { s+=c[x]; x-=lowbit(x); } return s; } int main() { int i,j,s,ca=0; while(~sfff(n,m,s),n+m+s) { printf(CASE #%d: ,++ca); for(i=1;i<=n;i++) a[i]=s; s=judge(s); mem(c,0); if(s) { for(i=1;i<=n;i++) update(i,s); } int op,le,ri; while(m--) { sfff(op,le,ri); if(op==0) { int cur=a[le]; int to=a[le]+ri; a[le]=to; cur=judge(cur); to=judge(to); if(cur==to) continue; if(cur) update(le,-1); else update(le,1); } else { pf(%d ,sum(ri)-sum(le-1)); } } printf( ); } return 0; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：POJ 2299 Ultra-QuickSort（逆序..	下一篇：[Practical.Vim(2012.9)].Drew.Ne..

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: