11610

To solve the problem indexes of the array are also needed to be updated and queried.

#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>

using namespace std;

struct RevPrime{
	int reversePrime;
	int factorCount;
};

int prime[1000001];
RevPrime arr[80000];
int Bit[2][80000];

vector<int> vb;
int k=1;

int reverse(int a)
{
	int num=0;
	while(a)
	{
		num*=10;
		num += (a%10);
		a/=10;
	}
	return num;
}

bool cmp(RevPrime a,RevPrime b)
{
	return a.reversePrime<b.reversePrime;
}

void update(int row,int idx,int val)
{
	while(idx<k)
	{
		Bit[row][idx]+=val;
		idx +=(idx & (-idx));
	}
}

int query(int row,int idx)
{
	int ret=0;
	while(idx>0)
	{
		ret+=Bit[row][idx];
		idx -= (idx & (-idx));
	}
	return ret;
}

int binarySearch(int lw,int hi,int val)
{
	if(hi<lw)
		return 0;
	int mid = (hi+lw)>>1;
	if(arr[mid].reversePrime<val)
	{
		return binarySearch(mid+1,hi,val);
	}
	else if(arr[mid].reversePrime>val)
	{
		return binarySearch(lw,mid,val);
	}
	else if(arr[mid].reversePrime==val)
		return mid;
	return 0;
}

int findIndex_bianarySearch(int lw,int hi,int modifiedIndex_value)
{
	if(hi<lw)
		return 0;
	int mid =(hi+lw)>>1;
	int mid_val=query(1,mid);
	if(mid_val<modifiedIndex_value)
		return findIndex_bianarySearch(mid+1,hi,modifiedIndex_value);
	else if(mid_val>modifiedIndex_value)
		return findIndex_bianarySearch(lw,mid,modifiedIndex_value);
	else
		return mid;
	return 0;
}

int main () {
    int b;
	int tmp;
    for(int i=2;i<1000001;i++)
    {
    	if(prime[i]==0)
    	{
    		prime[i]+=1;
    		vb.push_back(i);
    		for(int j=i+i;j<1000001;j+=i)
    		{
    			prime[j]+=1;
    			tmp=j/i;
    			while(tmp%i==0)
    			{
    				prime[j]+=1;
    				tmp/=i;
    			}
    		}
    	}
    }
    for(int i=0;i<vb.size();i++)
    {
    	b = reverse(vb[i]);
    	arr[k].factorCount=prime[b];
    	while(b<1000000)
    	{
    		b*=10;
    		arr[k].factorCount+=2;
    	}
    	arr[k].reversePrime=b;
    	k+=1;
    }
    sort(arr,arr+k,cmp);
    for(int i=1;i<k;i++)
    {
		update(0,i,arr[i].factorCount);
		update(1,i,1);
	}
    char ch;
    int n;
    while(scanf("%c", &ch)!=EOF)
    {
    	scanf("%d",&n);
    	if(ch=='q')
    	{
			int original_index=findIndex_bianarySearch(1,k,n+1);
    		cout<<query(0,original_index)<<"\n";
    	}
    	if(ch=='d')
    	{
    		int idx = binarySearch(1,k,n);
    		update(0,idx,(-1)*arr[idx].factorCount);
			update(1,idx,-1);

    	}
    }
    return 0;
}