Trie
学习资料
直接建立trie，记录名单的结尾，第一次点过后标记。
#include <cstdio>
#include <iostream>
#include <string>
#include <cstring>
using namespace std;
const int N=5e5+10;
int n,nex[N][40],cnt=1;
char s[100];
bool in[N],done[N];
int main()
{
// freopen("work.in","r",stdin); freopen("work.out","w",stdout);
scanf("%d",&n);
int u,c;
for(int i=1;i<=n;i++)
{
scanf(" %s",s);
u=1;
for(int j=0;s[j];j++)
{
c=s[j]-'a';
if(!nex[u][c]) nex[u][c]=++cnt;
u=nex[u][c];
}
in[u]=true;
}
scanf("%d",&n);
while(n--)
{
scanf(" %s",s);
u=1;
for(int j=0;s[j] && u;j++) u=nex[u][s[j]-'a'];
if(done[u]) puts("REPEAT");
else if(in[u]) {done[u]=true; puts("OK");}
else puts("WRONG");
}
// fclose(stdin); fclose(stdout);
return 0;
}
01-trie
这东西可以维护异或极值。
洛谷找不到这题，只有接下来要讲的进阶版。
题目非常简洁。
在给定的 $N$ 个整数 $A_1，A_2……A_N$ 中选出两个进行 $xor$（异或）运算，得到的结果最大是多少？
以下以李煜东蓝书中解释为基础。
将每一个数字转化成 $32$ 位二进制数插入trie树。对于每一个数字 $A_i$ ，插入后在trie树上尽量遍历与 $A_i$ 当前位相反的指针。
以上策略根据 $xor$ 运算“相同得 $0$ ，不同得 $1$”的性质得出。
至于为什么在查询前插入，是因为第一个数不会对之前插入的数进行统计，此时异或等于 $0$ 。
先dfs出每个节点从根到自己的异或路径做树上差分即可，trie的部分和上题没有什么差别。如果这题需要代码请回复在评论区或者私信。
可持久化字典树
在序列末尾添加一个数，这让我们想起主席树。
2操作刨区间也是主席树有的操作。
没错，这题是可持久化trie。
思路是OI Wiki的，代码则更加简洁，推荐一起食用。
#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int N=6e5+10;//双倍空间
int a[N],sum[N];
namespace trie
{
int cnt,rt[N],tr[N << 5][2],val[N << 5];
inline void ins(int o,int lst,int v)
{
for(int i=25,bit;~i;i--)
{
val[o]=val[lst]+1;
bit=(v>>i)&1;
if(!tr[o][bit]) tr[o][bit]=++cnt;
tr[o][bit^1]=tr[lst][bit^1];//复制
o=tr[o][bit]; lst=tr[lst][bit];
}
val[o]=val[lst]+1;
}
inline int query(int l,int r,int v)
{
int res=0;
for(int i=25,bit;~i;i--)
{
bit=(v>>i)&1;
//这里判断的写法是个好东西，即使你传参时lr写反了也没事
if(val[tr[r][bit^1]]-val[tr[l][bit^1]]) {res+=(1<<i); l=tr[l][bit^1]; r=tr[r][bit^1];}
else {l=tr[l][bit]; r=tr[r][bit];}
}
return res;
}
}
using namespace trie;//坏习惯
int main()
{
// freopen("work.in","r",stdscanfin); freopen("work.out","w",stdout);
int n,m,l,r,x;
char op;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) {scanf("%d",&a[i]); sum[i]=sum[i-1]^a[i];}//前缀异或和
for(int i=1;i<=n;i++) {rt[i]=++cnt; ins(rt[i],rt[i-1],sum[i]);}//复制修改路径版本
while(m--)
{
scanf(" %c",&op);
if(op == 'A')
{
scanf("%d",&a[++n]);
sum[n]=sum[n-1]^a[n];
rt[n]=++cnt; ins(rt[n],rt[n-1],sum[n]);
}
else
{
scanf("%d%d%d",&l,&r,&x);
l--; r--;
if(l == r && !l) printf("%d\n",sum[n]^x);
else printf("%d\n",query(rt[max(l-1,0)],rt[r],x^sum[n]));
}
}
// fclose(stdin); fclose(stdout);
return 0;
}
闲话
某天xgf突然发现01-trie可以实现平衡树，而且常数还贼小。
01-trie有左子树上的任何数小于右子树上的任何数的性质。
我太菜了不会实现，大家有兴趣实现了的话记得踢我让我开开眼界。
The End
关于其他trie的用法在OI Wiki中有介绍，由于作者还没学故没有出现在笔记中。接下来的话看心情更新。
