Untitled

#include<cstring>
#define ll long long
#define MS 13000
#define MT 1000002
using namespace std;
 
struct species{
    int id;
    int pid;
    int st;
    int en;
    int dist;
 
    int parent1;
    int parent10;
    int parent100;
 
    ll v;
    int next;
}S[MS];
int map[MS], nm;
int h;
ll uv;
 
int getID(char *s){
    ll v = 0;
    for (int i = 0; s[i]; i++) v = (v << 6) | (s[i] - 'A' + 1);
    uv = v;
    h = v%MS;
    int id = map[v%MS];
    while (id && S[id].v != uv) id = S[id].next;
    return id;
}
 
int interval, num, single[MT];
int secs[1003];
 
int c;
 
void update(int x, int delta)
{
    x += 1;
    for (; x <= MT; x += x&-x)
        single[x] += delta;
}
int query(int x)
{
    x += 1;
    int sum = 0;
    for (; x > 0; x -= x&-x)
        sum += single[x];
    return sum;
}
 
void init(char mAncestor[], int mDeathday)
{
    interval = 1000;
 
    for (register int i = 0; i <= MS; i++){
        map[i] = 0;
        S[i].v = 0;
        S[i].next = 0;
    }
    nm = 1;
    c = 1;
 
    memset(single, 0, sizeof(single));
    for (int i = 0; i < 10; i++) secs[i] = 0;
 
    int id = getID(mAncestor);
    if (!id){
 
        S[c].id = c;
        S[c].en = mDeathday;
        S[c].pid = -1;
        S[c].st = 0;
        S[c].dist = 0;
 
        S[c].v = uv;
        S[c].next = map[h];
        map[h] = c;
 
        //calcnt(0, mDeathday);
        update(0, 1);
        update(mDeathday+1, -1);
 
        c++;
    }
 
    return;
}
 
int add(char mName[], char mParent[], int mBirthday, int mDeathday)
{
 
    int pid = getID(mParent);
    int id = getID(mName);
    if (!id){
 
        id = c;
 
 
        S[c].id = c;
        S[c].en = mDeathday;
        S[c].pid = pid;
        S[c].st = mBirthday;
        S[c].dist = S[S[c].pid].dist + 1;
 
        S[c].parent1 = pid;
 
        if (S[pid].dist % 100 != 0)
            S[c].parent100 = S[pid].parent100;
        else
            S[c].parent100 = pid;
        if (S[pid].dist % 10 != 0)
            S[c].parent10 = S[pid].parent10;
        else
            S[c].parent10 = pid;
 
        //calcnt(mBirthday, mDeathday);
        update(mBirthday, 1);
        update(mDeathday+1, -1);
 
        S[c].v = uv;
        S[c].next = map[h];
        map[h] = c;
 
        c++;
    }
    return S[id].dist;
}
 
int distance(char mName1[], char mName2[])
{
    //int id1 = getID(mName1);// name[mName1];
    //int id2 = getID(mName2); // name[mName2];
 
    //int d = 0;
    //while (id1 != id2){
    //  if (id1 < id2) id2 = S[id2].pid;
    //  else id1 = S[id1].pid;
    //  d++;
    //}
 
 
    //return d;
    int p1 = getID(mName1),
        p2 = getID(mName2),
        d1 = S[p1].dist,
        d2 = S[p2].dist;
 
    // jump 100
    while (S[S[p1].parent100].dist <
        S[S[p2].parent100].dist)
        p2 = S[p2].parent100;
    while (S[S[p1].parent100].dist >
        S[S[p2].parent100].dist)
        p1 = S[p1].parent100;
    while (S[p1].parent100 != S[p2].parent100) {
        p2 = S[p2].parent100;
        p1 = S[p1].parent100;
    }
 
    // jump 10
    while (S[S[p1].parent10].dist <
        S[S[p2].parent10].dist)
        p2 = S[p2].parent10;
    while (S[S[p1].parent10].dist >
        S[S[p2].parent10].dist)
        p1 = S[p1].parent10;
    while (S[p1].parent10 != S[p2].parent10) {
        p2 = S[p2].parent10;
        p1 = S[p1].parent10;
    }
 
    // jump 1
    while (S[p1].dist > S[p2].dist)
        p1 = S[p1].parent1;
    while (S[p1].dist < S[p2].dist)
        p2 = S[p2].parent1;
    while (p1 != p2) {
        p1 = S[p1].parent1;
        p2 = S[p2].parent1;
    }
    return d1 + d2 - S[p1].dist - S[p2].dist;
}
 
int count(int mDay)
{
    return query(mDay);
}