hoj 1867ハルビン工業大学ojマネージャーの悩み簡単な樹状配列

社長の悩み
My Tags
(Edit)   Cancel - Seperate tags with commas.
 
Source : HCPC 2005 Spring
 
Time limit : 2 sec
 
Memory limit : 32 M
Submitted : 1961, Accepted : 455
Jerryは会社の販売部門のマネージャーです.この会社にはチェーン店がたくさんあります.番号は1、2、3です.Jerryは毎日各チェーン店の商品数とその変化に注目しなければならない.退屈な仕事だ.チェーン店が比較的少ない時、Jerryは番号が[i,j]区間内のチェーン店の中で商品数が素数の何軒かを計算するのが好きだったが、現在チェーン店の数が急激に増加し、計算量が大きく、Jerryは結果を出すのが難しい. 
入力フォーマットのタイトルには複数の入力があります.各組は第1行を入力して3つの整数があります:Cチェーン店の数量N指令の条数M各チェーン店の初期の商品の数量は次にN行があって、1行ごとに1本の指令があります.指令のフォーマットは、0 x yチェーン店xの商品数変化値がy,y>0商品数増加、y<0減少1 i j出力番号が[i,j]区間内のチェーン店の商品数が素数のものが何軒あるか1<=i,x,j<100000チェーン店の商品数aが0<=a<1000000,C=N=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

単純な木配列の応用は素数を判断する元は素数であるが後に素数ではない-1元は素数ではない後に素数になる+1注意0 1の2つの素数ではない特殊な状況
post code

/*This Code is Submitted by 1115332213 for Problem 1867 at 2012-09-05 23:18:52*/
#include<stdio.h>
#include<math.h>
#include<string.h>
int a[1000010],c,b[1000010];
int  isprime(int  a)   //     
{    
     int i;
     int n=int(sqrt( (double)(a) ));
     for(i=2; i<n+1; i++ )
     {
       if(a%i==0){return 0;}         
     }
     return 1;
}

int lowbit(int t)
{
  return t&(t^(t-1));    
}

int insert(int pos ,int num)
{
    while( pos<=c )
    {
      a[pos]+=num;
      pos+=lowbit(pos);             
    }    
}

int query( int pos)
{
    int sum=0;
    while( pos>0 )    
    {
      sum+=a[pos];
      pos-=lowbit(pos);       
    }
    return sum;
    
}


int main()
{
    int n,m,i,ji=0,judge,pos,num,beg,end ,flag1,flag2;
    while(scanf("%d %d %d",&c,&n,&m))
    {
        if(c==0&&n==0&&m==0)break;
        for( i=1; i<1000010; i++)
           b[i]=m;
        ji++;
        printf("CASE #%d:
",ji);   
        memset( a, 0, sizeof(a) );
        if( isprime(m)==1 &&m!=0&&m!=1 ){
                                 for( i=1; i<=c; i++ )
                                 {
                                  insert(i,1);     
                                 }     
                                       }     
        for( i=1; i<=n; i++ )
        {
             scanf("%d",&judge);
             if(judge==0){
                           flag1=flag2=0;
                           scanf("%d %d",&pos,&num);
                           if( isprime(b[pos] )==1&&b[pos]!=0&&b[pos]!=1 )flag1=1;

                           b[pos]+=num;
                           if(isprime( b[pos] )==1&&b[pos]!=0&&b[pos]!=1) flag2=1; 
      
                           if( flag1==1 && flag2==0 )insert( pos,-1 );    //-1
                           if( flag1==0 && flag2==1 )insert( pos, 1 );    //+1
                         }
             else {
                     scanf("%d %d",&beg,&end);
                     printf("%d
",query(end)-query(beg-1));
                  
                  
                  }
             
             
             
        }
        printf("
");
                    
                    
    }
         
}