3485.最大异或和
思路：利用前缀数组S（异或）的思想，要求某个区间的数的异或和，可以用区间的两个端点的S值进行异或。（这个地方注意边界）。
怎么在限制范围内求两个Si值的异或的最大值呢。
利用字典树的思想，让字典树的cnt数组保存这个结点出现的次数。
在二叉树中找结果（具体做法就是从高位到低位尽量找和当前的数不同的分支），可能存在找到不在区间内的S值。我们可以从1到n遍历，删掉没有用的，而且后面也不会用到了。
debug ：res*=2+1 和 res=res*2+1不一样，后者等于 res=res*(res*2+1);
#include<bits/stdc++.h>
using namespace std;
const int N=100010*31,M=100010;
//3485最大异或和
int p[N][32];
int cnt[N];
int a[N],s[N];
int n,m;
int idx=0;
//注意边界问题：si和sj异或后的结果是i到j-1的异或和
//所以每次删除的是i-m-1位置的数。
//因为从m+1就有需要删除的了此时考虑到用到了s0，所以先要把s0删除void insertt(int x,int t)
{int f=0;//因为本来父节点就为0for(int i=30;i>=0;i--){int u=x>>i&1;//获取第i位的二进制值if(!p[f][u])p[f][u]=++idx;f=p[f][u];cnt[f]+=t;//插入的时候某个节点出现一次就加1，要删除就-1}
}int query(int x)
{int f=0;int res=0;for(int i=30;i>=0;i--){int u=x>>i&1;if(cnt[p[f][!u]])//和x的第i位不同的分支存在{//这个判断条件不可以直接用p数组。//可能已经把经过这个结点的数删没了，但是p还是有值的。res=2*res+1;f=p[f][!u];}else{res*=2;f=p[f][u];}}return res;
}int main()
{cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i];s[i]=s[i-1]^a[i];}insertt(s[0],1);int ans=-1*N;for(int i=1;i<=n;i++){if(i>m)insertt(s[i-m-1],-1);ans=max(ans,query(s[i]));insertt(s[i],1);}cout<<ans<<endl;}
835 Trie字符串统计（第一个独立写出的字典树）
#include<bits/stdc++.h>
using namespace std;
//835字符串统计
const int N=100010;
char f[N][30];
int cnt[N];
int idx=0;
void insertt(string s)
{int p=0;for(int i=0;i<s.length();i++){if(!f[p][s[i]-'a'])f[p][s[i]-'a']=++idx;p=f[p][s[i]-'a'];}cnt[p]++;
}int query(string s)
{int p=0;for(int i=0;i<s.length();i++){if(f[p][s[i]-'a'])p=f[p][s[i]-'a'];else return 0;}return cnt[p];
}
int main()
{int n;cin>>n;while(n--){string s;char c;cin>>c;cin>>s;if(c=='I'){insertt(s);}else{cout<<query(s)<<endl;}}
}
143最大异或对
开始的时候在insert和query把获取各个位的边界和遍历方向弄错了；
（先做第一个后面两道都做的很快）
#include<bits/stdc++.h>
using namespace std;
//143最大异或对
const int N=1e5+10,M=3e6+10;
int f[M][3];
int cnt[N];
int idx=0;
void insertt(int x)
{int p=0;for(int i=30;i>=0;i--){int u=x>>i&1;if(!f[p][u])f[p][u]=++idx;p=f[p][u];cnt[p]++;}
}//找当前数的最大异或和
int query(int x)
{int p=0;int res=0;for(int i=30;i>=0;i--){int u=x>>i&1;if(f[p][!u]){res=res*2+1;p=f[p][!u];}else{res*=2;p=f[p][u];}}return res;
}int main()
{int n;cin>>n;int ans=0;while(n--){int num;cin>>num;insertt(num);ans=max(ans,query(num));}cout<<ans<<endl;
}
