Algorithm_Code_Templates/PersistentTrie.cpp at master · hasinur010/Algorithm_Code_Templates · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
/*

  AUTHOR: MD. HASINUR RAHMAN, RUET'15
  Tested problem: Codechef -> XORMIN

*/
#define lim 200010
/// NODE =  trie nodes
struct NODE
{
    LL f,num;
    NODE *nxt[2];
    NODE()
    {
        f = num = 0;
        nxt[0] = nxt[1] = NULL;
    }
};


NODE *roots[lim]; /// Head of each state
LL a[lim]; /// information array


void Insert( LL pos )
{
    roots[pos] = new NODE;

    NODE *p = roots[pos];

    p->nxt[0] = (roots[pos-1])->nxt[0];

    p->nxt[1] = (roots[pos-1])->nxt[1];

    for( LL i = 20 ; i>=0 ; i-- )
    {
        LL b = CHK(a[ pos ],i)?1:0;
        if( p->nxt[b] == NULL )
        {
            p->nxt[b] = new NODE;
        }
        else
        {
            NODE *q = new NODE;

            q->f = (p->nxt[b])->f;
            q->nxt[0] = (p->nxt[b])->nxt[0];
            q->nxt[1] = (p->nxt[b])->nxt[1];
            p->nxt[b] = q;

        }
        p = p->nxt[b];
        (p->f)++;
    }
    p->num = a[ aof[pos] ];
}


/// Finds maximum a[i] xor K
LL Search( LL L, LL R, LL K )
{

    NODE *LP = roots[L-1], *RP = roots[R];
    for( LL i = 20 ; i>=0 ; i-- )
    {
        LL b = CHK(K,i)?1:0;
        LL lagbe = b^1;
        if( LP == NULL || LP->nxt[lagbe] == NULL )
        {
            if( RP->nxt[lagbe] != NULL )
            {
                RP = RP->nxt[lagbe];
                LP = NULL;
            }
            else
            {
                if(LP!=NULL)
                    LP = LP->nxt[b];
                RP = RP->nxt[b];
            }
        }
        else
        {
            if( RP->nxt[lagbe] != NULL )
            {
                if( (LP->nxt[lagbe])->f < (RP->nxt[lagbe])->f )
                {
                    LP = LP->nxt[lagbe];
                    RP = RP->nxt[lagbe];
                }
                else
                {
                    LP = LP->nxt[b];
                    RP = RP->nxt[b];
                }
            }
            else
            {
                LP = LP->nxt[b];
                RP = RP->nxt[b];
            }
        }

    }
    return (RP->num) ^ K;

}