程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> Hoj 1867 經理的煩惱（樹狀數組）

Hoj 1867 經理的煩惱（樹狀數組）

編輯：C++入門知識

Hoj 1867 經理的煩惱（樹狀數組）

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;
}