字典树 tire

(参考https://blog.csdn.net/u013588639/article/details/38406453，https://blog.csdn.net/guhaiteng/article/details/52191831）

int ch[32*N][27];  //节点编号   
int sz;        //字典树节点个数
int val[32*N];   //节点的值

void init()
{
    sz=1;
    memset(ch,0,sizeof(ch));
    memset(val,0,sizeof(val));
}
void insert(char *s)
{
    int u=0,c;
    for(int i=0;i<strlen(s);i++)
    {
        c=s[i]-'a';
        if(!ch[u][c])
            ch[u][c]=sz++;
        u=ch[u][c];
        val[u]++;       
    }
}
int query(char *s)
{
    int u=0,c;
    for(int i=0;i<strlen(s);i++)
    {
        c=s[i]-'a';
        if(!ch[u][c])
            return 0;
        u=ch[u][c];
    }
    return  val[u];
}

一.模版题
题目:http://hihocoder.com/problemset/problem/1014
code：http://hihocoder.com/problemset/solution/1413717

二.最大异或和
解决异或和的问题要用到01字典树，其他形式搞都不太对。
https://blog.csdn.net/guhaiteng/article/details/52191831这篇文章里模版蛮好的，就抄一下，记录一下。

#define Memset(x, a) memset(x, a, sizeof(x))
typedef long long ll;
const int maxn = 100000 + 5;//集合中的数字个数
int ch[32*maxn][2];         //节点的边信息
ll val[32*maxn];            //节点存储的值
ll cnt[32*maxn];          //节点出现的次数
int sz;                     //树中当前节点个数
 
void init(){
    Memset(ch[0],0);           //树清空
    Memset(cht,0); 
    sz=1;
}
 
void _insert(ll a){//在字典树中插入 a
                  //和一般字典树的操作相同 将X的二进制插入到字典树中
    int u=0;
    for(int i=32;i>=0;i--){
        int c=((a>>i)&1);
        if(!ch[u][c]){
            Memset(ch[sz],0);
            val[sz]=0;
            ch[u][c]=sz++;
        }
        u=ch[u][c];
        cnt[u]++;
    }
    val[u]=a;     //最后的节点插入value
}
 void _del(ll a)
{
     int u=0;
     for(int i=32;i>=0;i--){
            int c=((a>>i)&1);
        u=ch[u][c];
        cnt[u]--;
     }
}
ll query(ll a){   //在字典树中查找和a异或的值最大的元素b 返回b的值
    int u=0;
    for(int i=32;i>=0;i--){
        int c=((a>>i)&1);
        if(ch[u][c^1]&&cnt[ch[u][c^1])   u=ch[u][c^1];
        else u=ch[u][c];
    }
    return val[u];
}

总的来说就是插入的时候，数倒着插，保证“头大”，可以先当32位数来弄，保证对齐，查询的时候，尽量走反的路。
题目：http://hihocoder.com/problemset/problem/1860
code：http://hihocoder.com/problemset/solution/1413750
查找一段数组中连续数的最大异或和，先把每个前缀异或插入01字典树，然后直接按每个前缀进行搜，0也算前缀，这个不要忘记。

1.hdu5536 Chip Factory
题目:https://vjudge.net/problem/HDU-5536
code：https://paste.ubuntu.com/p/ntCzdhpStY/
枚举两维，因为三个数要求不同，需要用删除操作。

2.CF 706 D. Vasiliy's Multiset
题目: http://codeforces.com/contest/706/problem/D
code:http://codeforces.com/contest/706/submission/45062109