学步园

有一些7位数，倒转过之后都是小于10^6的素数，叫做倒素数。把这些倒素数按大小排列，分别求出每个倒素数的素因子个数（比如24是2,2,2,3，共4个）；

先有两种操作：

1.q i：查询从第0个到第i个倒素数的所有素因子之和；

2.d x：从这些倒素数中删除x，剩下的倒素数按大小重新排列。

首先把每个倒素数除以10，然后因子个数都先加上2，消除末尾0（题目也是有点无聊）；

delete操作add函数可以完成；

主要是删除之后剩下的数重新排列有点麻烦，但是不是不可解决：

1.建立一个维护名次的树状数组，sum(x)就是x的名次，所以初始化的之和每个点都直接更新1，删除的时候直接更新-1；

2.询问真的名次时，则需要二分查找出初始名次，sum函数求出来的数组必然有序，所以需要一个类似于upper_bound的函数（同一值的点必然最后一个是合法的）。

要实现lower_bound和upper_bound的功能只差在等号加在哪个if上。

#include <algorithm>
#include <stdlib.h>
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <math.h>
using namespace std;
#define MAXN 670000
#define lowbit(x) (x & -x)
#define bin(x) (lower_bound(rev, rev + tot, x) - rev)

/*.............................................PRIME SIEVE.............................................*/
const int maxn = 1000100;
const int prin = 300000;

int prime[prin];
///仅包含奇数，isprime[k]代表2*k+3
bool isprime[maxn>>1];
int ptop = 0;

void sieve()
{
        memset(isprime, true, sizeof(isprime));
        prime[0] = 2;
        int sq = sqrt(maxn);
        for(int i = 3; i < maxn; i += 2)
        {
                if(isprime[(i-3)>>1])
                {
                        if(i <= sq+3)
                        {
                                for(int j = i*i; j < maxn; j += 2*i)
                                {
                                        isprime[(j-3)>>1] = false;
                                }
                        }
                        prime[++ptop] = i;
                }
        }
        return ;
}

/*.............................................PRIME SIEVE.............................................*/

int rev[MAXN], fac[MAXN], ss[MAXN], in[MAXN];
int tot;

int sum(int a[], int i)
{
    int ret = 0;
    while(i > 0) ret += a[i], i -= lowbit(i);
    return ret;
}

int add(int a[], int i, int val)
{
    while(i <= tot) a[i] += val, i += lowbit(i);
}

int get_rev(int x)
{
    int ret = 0;
    for(int i = 0; i < 6; i++) ret *= 10, ret += x % 10, x /= 10;
    return ret;
}

void init()
{
    sieve();

    for(tot = 0; prime[tot] < 1000000; tot++) rev[tot] = get_rev(prime[tot]);
    sort(rev, rev + tot);

    for(int i = 0; i < tot; i++)
    {
        fac[i] = 2; //已去掉末尾0
        int tmp = rev[i];
        for(int j = 0; prime[j] <= sqrt(tmp + 10); j++)
            while(tmp % prime[j] == 0) tmp /= prime[j], fac[i]++;
        if(tmp > 1) fac[i]++;
    }

    for(int i = 0; i < tot; i++) add(ss, i + 1, fac[i]), add(in, i + 1, 1);
}

int find(int x, int l = 1, int r = tot + 1)
{
    if(l >= r) return r;
    int m = (l + r) >> 1;
    if(sum(in, m) >  x) return find(x, l, m);
    if(sum(in, m) <= x) return find(x, m + 1, r);
}

char op[4];
int x;

int main()
{
//    freopen("D.in", "r", stdin);
//    freopen("D.out", "w", stdout);

    init();
    while(~scanf("%s%d", op, &x))
    {
        if(op[0] == 'q')
        {
            int id = find(x + 1) - 1;
            printf("%d\n", sum(ss, id));
        }
        if(op[0] == 'd')
        {
            x /= 10;
            int id = bin(x);
            add(ss, id + 1, -fac[id]);
            add(in, id + 1, -1);
        }
    }
    return 0;
}