UVa11610

UVa11610
初BIT(Binary Index Tree)
もう少し賢い実装ができなかったものかと、反省。

// UVa 11610
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <iterator>

using namespace std;

const int P = 1000000;
const int Q = 100000000;
bool prime[P];
int rp[P];
int rp_fact[P];
map<int, int> rp_idx;
int fact[Q];

void sieve(void)
{
  fill(prime, prime + P, true);
  prime[0] = prime[1] = false;  

  for (int i = 2; i * i < P; ++i) {
    for (int j = 2; i * j < P; ++j) {
      prime[i * j] = false;
    }
  }

  return ;
}

int make_revprime(void)
{
  int size = 0;
  for (int i = 1000000; i<10000000; ++i) {
    int n = 0;
    int m = i;
    while (m) {
      n = n * 10 + m % 10;
      m /= 10;
    }
    if (P <= n) continue;
    if (prime[n]) {
      rp_idx[i] = size;
      rp[size++] = i;
    }
  }
  return size;
}

void cnt_fact(const int rp_size)
{
  const int size = count(prime, prime + P, true);
  int p[size];
  for (int i = 0, j = 0; i < P; ++i) {
    if (prime[i]) {
      p[j++] = i;
      fact[i] = 1;
    }
  }
     
  for (int i = 2; i < P; ++i) {
    for (int j = 0; i * p[j] < P; ++j) {
      fact[i * p[j]] = fact[i] + 1;
    }
  }

  for (int i = 0; i < rp_size; ++i) {
    int n = rp[i];
    for (int j = 0; j < size && P <= n; ++j) {
      while (n % p[j] == 0) {
        ++rp_fact[i];
        n /= p[j];
      }
    }
    if (n < P) rp_fact[i] += fact[n];
    else ++rp_fact[i];
    fact[rp[i]] = rp_fact[i];
  }

  return ;
}

// num of reverse primes
const int N = 78498 + 1;
namespace BIT {
  // tree[] is 1-origine
  int tree[N];

  inline
  int lastOne(int i)
  {
    return i & -i;
  }

  void build(int val[], int size) 
  {
    // sum[] is 1-origine
    int sum[N];
    sum[1] = val[0];
    for (int i = 2; i < N; ++i) {
      sum[i] = sum[i-1] + val[i-1];
    }
    for (int i = 1; i < N; ++i) {
      int j = i - lastOne(i) + 1;
      tree[i] = sum[i] - sum[j] + val[j-1];
    }
    return ;
  }

  // query is 0-origine
  void update(int n, int v)
  {
    ++n;
    while (n < N) {
      tree[n] += v;
      n += lastOne(n);
    }
    return ;
  }
   
  // query is 0-origine
  int query(int n)
  {
    ++n;
    int sum = 0;
    while (0 < n) {
      sum += tree[n];
      n -= lastOne(n);
    }
    return sum;
  }
};

int main(void)
{
  sieve();
  const int rp_size = make_revprime();
  cnt_fact(rp_size);

  BIT::build(rp_fact, rp_size);
   
  set<int> removed_idx;
  int n;
  char c;
  while (cin >> c >> n) {

    if (c == 'q') {
      for (set<int>::iterator itr = removed_idx.begin();
           itr != removed_idx.end();
           ++itr) {
        if (*itr <= n) ++n;
        else break;
      }
      
      cout << BIT::query(n) << endl;
    }
    else {
      removed_idx.insert(rp_idx[n]);
      BIT::update(rp_idx[n], -fact[n]);
    }
  }

  return 0;
}