Trie 学习笔记
在此记录若干 Trie 好题。
1. 洛谷 P3732 [HAOI2017] 供给侧改革
点击查看题面
给定一个长度为 \(n\) 的 \(\texttt{01}\) 字符串 \(S\)。
令 \(\operatorname{data}(L, R)\) 表示：在字符串 \(S\) 中，起始位置在 \([L, R]\) 之间的这些后缀之中，具有最长公共前缀的两个后缀的最长公共前缀的长度。
给定 \(q\) 个询问，对于每一个询问 \(L, R\)，求：
\(1 \leq n, q \leq 10^5\)，\(\texttt{01}\) 串随机生成。
点击查看题解
开一棵 Trie 树，记录当前插入的每个后缀。
由于数据随机，对于任意 \(l, r\)，\(\operatorname{data}(l, r)\) 的值一定不会太大。因此我们只插入每个后缀的前 \(40\) 个字符。
将询问离线，从小到大依次插入每个后缀 \(R\)。在每次插入后处理每个右端点为 \(R\) 的询问。
开一棵线段树，第 \(L\) 位表示 \(\operatorname{data}(L, R)\) 的值。则询问 \(L, R\) 即为求线段树上 \([L, R - 1]\) 的和。
考虑每次插入后缀 \(R\) 后，对线段树有什么影响。显然每个位置的意义由 \(\operatorname{data}(L, R - 1)\) 变为 \(\operatorname{data}(L, R)\)。
对于以 \(L\) 为左端点的 \(\operatorname{data}\) 值，相当于新增了 \((L, R), (L + 1, R), \cdots ,(R - 1, R)\) 这些匹配，需要依次对它们的 LCP 值取 \(\max\)。而一个前缀可以用 Trie 树的一个结点上表示。
因此只需在 Trie 的每个结点上记录下：经过该结点的所有后缀编号（即开始的下标）\(p_1, p_2, p_3, \cdots, p_k\)，插入 \(R\) 时对遍历到的每个结点，对线段树上 \([1, p_1], [1, p_2], \cdots, [1, p_k]\) 这些区间，用该结点进行更新即可。
而由于这是取 \(\max\) 而不是计数，只需保留这些 \(p_i\) 中的最大值即可。
因此做法即为：将询问离线并按 \(R\) 排序，在 Trie 的结点上记录最后访问该点的后缀 \(p_u\)。每次插入后缀 \(R\) 时，对访问的每个结点 \(u\)，更新线段树上区间 \([1, p_u]\) 的值。询问答案即为线段树的后缀和。
时间复杂度为 \(\Theta((40n + q) \log n)\)。
点击查看代码
#include <algorithm>
#include <cstdio>
#include <iostream>
using namespace std;
const int N=100003,M=40;
struct Question{
int l,r,p;
}qu[N];
struct SGT{
int l,r,minn,maxn,sum,val;
}node[N*4];
char a[N];
int n,q,ans[N],f[N*M];
int len_trie=0,trie[N*M][2];
bool cmp(const Question& a,const Question& b){
return a.r<b.r;
}
void update(int u,int x){
if(x<=node[u].val) return ;
node[u].minn=node[u].maxn=node[u].val=x;
node[u].sum=x*(node[u].r-node[u].l+1);
}
void push_up(int u){
int l=u*2,r=u*2+1;
node[u].minn=min(node[l].minn,node[r].minn);
node[u].maxn=max(node[l].maxn,node[r].maxn);
node[u].sum=node[l].sum+node[r].sum;
}
void push_down(int u){
int l=u*2,r=u*2+1;
update(l,node[u].val);
update(r,node[u].val);
node[u].val=0;
}
void build(int u,int l,int r){
node[u].l=l,node[u].r=r;
node[u].val=node[u].sum=0;
node[u].minn=node[u].maxn=0;
if(l<r){
int mid=(l+r)/2;
build(u*2 ,l,mid );
build(u*2+1,mid+1,r);
}
}
void modify(int u,int l,int r,int x){
if(node[u].l>=l&&node[u].r<=r)
if(node[u].maxn<=x){
update(u,x); return ;
}
else if(node[u].minn>=x) return ;
push_down(u);
int mid=(node[u].l+node[u].r)/2;
if(l<=mid) modify(u*2 ,l,r,x);
if(r> mid) modify(u*2+1,l,r,x);
push_up(u);
}
int query(int u,int l,int r){
if(node[u].l>=l&&node[u].r<=r)
return node[u].sum;
push_down(u);
int mid=(node[u].l+node[u].r)/2,ans=0;
if(l<=mid) ans+=query(u*2 ,l,r);
if(r> mid) ans+=query(u*2+1,l,r);
return ans;
}
void insert(int p){
int cur=0,i;
for(i=p;i<p+M&&i<=n;i++){
if(trie[cur][a[i]-'0']==0)
trie[cur][a[i]-'0']=++len_trie;
cur=trie[cur][a[i]-'0'];
if(f[cur]>0) modify(1,1,f[cur],i-p+1);
f[cur]=p;
}
}
int main(){
// freopen("reform.in","r",stdin);
// freopen("reform.out","w",stdout);
int i,j;
scanf("%d%d%s",&n,&q,&a[1]);
for(i=1;i<=q;i++){
scanf("%d%d",&qu[i].l,&qu[i].r);
qu[i].p=i;
}
build(1,1,n);
sort(qu+1,qu+q+1,cmp);
for(i=1,j=1;i<=q;i++){
while(j<=qu[i].r) insert(j++);
ans[qu[i].p]=query(1,qu[i].l,qu[i].r-1);
}
for(i=1;i<=q;i++)
printf("%d\n",ans[i]);
// fclose(stdin);
// fclose(stdout);
return 0;
}
2. 洛谷 P4592 [TJOI2018] 异或
点击查看题面
现在有一颗以 \(1\) 为根节点、由 \(n\) 个节点组成的树，节点从 \(1\) 至 \(n\) 编号。树上每个节点上都有一个权值 \(v_i\)。现在有 \(q\) 次操作，操作如下：
- \(1~x~z\)：查询节点 \(x\) 的子树中的节点权值与 \(z\) 异或结果的最大值。
- \(2~x~y~z\)：查询节点 \(x\) 到节点 \(y\) 的简单路径上的节点的权值与 \(z\) 异或结果最大值。
\(2 \leq n, q \leq 10^5\)，\(1 \leq v_i, z < 2^{30}\)。
点击查看题解
发现该题只有查询操作，没有修改操作。因此考虑建两颗可持久化 Trie。
预处理出：\(\mathrm{dfn}(u)\) 表示 \(u\) 的 dfs 序，\(\mathrm{son}(u)\) 表示 \(u\) 的子树中除 \(u\) 外有多少个点，以及倍增求 LCA 的数组。
对于操作 1：在 dfs 序上建立可持久化 Trie，只需查询版本 \([\mathrm{dfn}(x), \mathrm{dfn}(x) + \mathrm{son}(x)]\) 即可。
对于操作 2：每个点的版本从它父亲的版本上继承过来，只需查询版本 \([\operatorname{LCA}(x, y), x]\) 和 \([\operatorname{LCA}(x, y), y]\) 即可。
时间复杂度为 \(\Theta((n + q)\log V)\)，其中 \(V\) 表示值域。
点击查看代码
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int N=100003,M=30,log_N=18;
struct Trie{
int len_trie=0,trie[N*(M+3)][2],root[N];
void insert(int la,int cur,int x){
int p=root[la],q=root[cur]=++len_trie,i;
trie[q][0]=trie[p][0],trie[q][1]=trie[p][1];
for(i=M-1;i>=0;i--){
trie[q][x>>i&1]=++len_trie;
p=trie[p][x>>i&1],q=trie[q][x>>i&1];
trie[q][0]=trie[p][0],trie[q][1]=trie[p][1];
}
}
int query(int l,int r,int x){
int p=root[l],q=root[r],i,ans=0;
for(i=M-1;i>=0;i--)
if(trie[p][!(x>>i&1)]!=trie[q][!(x>>i&1)]){
p=trie[p][!(x>>i&1)];
q=trie[q][!(x>>i&1)];
ans|=1<<i;
}
else{
p=trie[p][x>>i&1];
q=trie[q][x>>i&1];
}
return ans;
}
}tr_dfn,tr_rot;
int n,q,a[N],ance[N][log_N],dep[N],son[N];
int len_list=0,e[N*2],ne[N*2],h[N];
int len_arr=0,arr[N],dfn[N];
void add_once(int a,int b){
e[len_list]=b;
ne[len_list]=h[a];
h[a]=len_list++;
}
void add_twice(int a,int b){
add_once(a,b);
add_once(b,a);
}
void dfs(int u,int fa,int depth){
dep[u]=depth,ance[u][0]=fa,son[u]=0;
for(int i=1;i<log_N;i++)
ance[u][i]=ance[ance[u][i-1]][i-1];
arr[++len_arr]=u,dfn[u]=len_arr;
tr_dfn.insert(len_arr-1,len_arr,a[u]);
tr_rot.insert(fa,u,a[u]);
for(int i=h[u];i>=0;i=ne[i])
if(e[i]!=fa) dfs(e[i],u,depth+1);
for(int i=h[u];i>=0;i=ne[i])
if(e[i]!=fa) son[u]+=son[e[i]]+1;
}
int LCA(int u,int v){
if(dep[u]<dep[v]) swap(u,v);
if(dep[u]>dep[v])
for(int i=log_N-1;i>=0;i--)
if(dep[u]-(1<<i)>=dep[v])
u=ance[u][i];
if(u==v) return u;
for(int i=log_N-1;i>=0;i--)
if(ance[u][i]!=ance[v][i])
u=ance[u][i],v=ance[v][i];
return ance[u][0];
}
int main(){
// freopen("xor.in","r",stdin);
// freopen("xor.out","w",stdout);
int i,x,y,opt,num,s1,ans;
scanf("%d%d",&n,&q);
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
memset(h,-1,sizeof h);
for(i=1;i<n;i++){
scanf("%d%d",&x,&y);
add_twice(x,y);
}
dfs(1,0,1);
for(i=1;i<=q;i++){
scanf("%d",&opt);
switch(opt){
case 1:
scanf("%d%d",&x,&num);
printf("%d\n",tr_dfn.query(dfn[x]-1,dfn[x]+son[x],num));
break;
case 2:
scanf("%d%d%d",&x,&y,&num);
s1=LCA(x,y),ans=a[s1]^num;
ans=max(ans,tr_rot.query(s1,x,num));
ans=max(ans,tr_rot.query(s1,y,num));
printf("%d\n",ans);
}
}
// fclose(stdin);
// fclose(stdout);
return 0;
}
3. 洛谷 P5283 [十二省联考 2019] 异或粽子
点击查看题面
给定一个长度为 \(n\) 的数组 \(a\)。
定义一个区间 \([l, r]\) 的权值为：对 \(i \in [l, r]\)，所有 \(a_i\) 的异或和。
给定 \(k\)，求若选择 \(k\) 个不同的区间，它们的权值之和的最大值。
数据保证一定有解。
\(1 \leq n \leq 5 \times 10^5\)，\(1 \leq k \leq \min \{ \dfrac{n(n - 1)}{2}, 2 \times 10^5 \}\)，\(0 \leq a_i < 2^{32}\)。
点击查看题解
仿照超级钢琴的做法，我们令 \(S_i\) 表示所有以 \(i\) 为右端点的区间构成的集合。
我们再开一个大根堆，将每个 \(S_i\) 中权值最大的区间丢进大根堆中。
易得此时大根堆的最大值即为所有区间的最大值。
重复 \(k\) 次以下步骤：
- 取出此时大根堆中的最大区间 \([l, r]\)。
- 将 \([l, r]\) 从堆和集合 \(S_i\) 中删去。
- 求出删去 \([l, r]\) 后 \(S_r\) 中的最大值，并将其加入堆中。
容易发现，第 \(i\) 执行完上述步骤后，当前的大根堆中的最大值一定是删去前 \(i\) 大的区间后所有区间的最大值，即所有区间的第 \(i + 1\) 大值。因此算法正确。
实现时不用真正维护 \(S_i\)。只需用 Trie 维护 \(a_i\) 的前缀异或和，每次循环时求出与 \(a_r\) 异或之后，比 \(a_{l - 1}\) 小的最大值。
时间复杂度为 \(\Theta((n + k)(\log V + \log n)\)，其中 \(V\) 为值域。
点击查看代码
#include <cstdio>
#include <iostream>
using namespace std;
const int N=500003,M=32;
int n,m,len_trie=0,trie[N*M][2],cnt[N*M],c[N];
unsigned int a[N],b[N];
struct Heap{
int n,p[N];
void up(int u){
while(u>1&&(a[p[u]]^b[p[u]])>(a[p[u/2]]^b[p[u/2]]))
swap(p[u],p[u/2]),u/=2;
}
void down(int u){
while(u*2<=n&&(a[p[u]]^b[p[u]])<(a[p[u*2]]^b[p[u*2]])||
u*2<n&&(a[p[u]]^b[p[u]])<(a[p[u*2+1]]^b[p[u*2+1]]))
if(u*2==n||(a[p[u*2]]^b[p[u*2]])>(a[p[u*2+1]]^b[p[u*2+1]]))
swap(p[u],p[u*2]),u*=2;
else
swap(p[u],p[u*2+1]),u=u*2+1;
}
void push(int x){ p[++n]=x; up(n); }
void pop(){ p[1]=p[n--]; down(1); }
int top(){ return p[1]; }
}hp;
void insert(unsigned int x){
int cur=0,i;
for(i=M-1;i>=0;i--){
if(trie[cur][x>>i&1]==0)
trie[cur][x>>i&1]=++len_trie;
cur=trie[cur][x>>i&1];
}
cnt[cur]++;
}
unsigned int query(unsigned int x,int& val){
int cur=0,i; unsigned int ans=0;
for(i=M-1;i>=0;i--)
if(trie[cur][!(x>>i&1)]>0){
cur=trie[cur][!(x>>i&1)];
ans|=(x&(1u<<i))^(1u<<i);
}
else{
cur=trie[cur][x>>i&1];
ans|=x&(1u<<i);
}
val=cnt[cur]-1; return ans;
}
bool to_next(unsigned int x,unsigned int& ans,int& val){
if(val>0){ val--; return 1; }
int cur=0,i,minn=M;
for(i=M-1;i>=0;i--){
if((ans>>i&1)!=(x>>i&1))
if(trie[cur][x>>i&1]>0) minn=i;
cur=trie[cur][ans>>i&1];
}
if(minn==M) return 0;
for(i=M-1,cur=0;i>minn;i--)
cur=trie[cur][ans>>i&1];
ans&=~((1u<<minn)-1),ans^=1u<<minn;
cur=trie[cur][x>>minn&1];
for(i=minn-1;i>=0;i--)
if(trie[cur][!(x>>i&1)]>0){
cur=trie[cur][!(x>>i&1)];
ans|=(x&(1u<<i))^(1u<<i);
}
else{
cur=trie[cur][x>>i&1];
ans|=x&(1u<<i);
}
val=cnt[cur]-1; return 1;
}
int main(){
// freopen("zongzi.in","r",stdin);
// freopen("zongzi.out","w",stdout);
int i,s1; long long ans=0;
scanf("%d%d",&n,&m),m*=2;
for(i=1;i<=n;i++){
scanf("%u",&a[i]);
a[i]^=a[i-1];
}
for(i=0;i<=n;i++) insert(a[i]);
for(i=0;i<=n;i++)
b[i]=query(a[i],c[i]);
for(i=0;i<=n;i++) hp.push(i);
for(i=1;i<=m;i++){
s1=hp.top(),hp.pop();
ans+=a[s1]^b[s1];
if(to_next(a[s1],b[s1],c[s1]))
hp.push(s1);
}
printf("%lld",ans/2);
// fclose(stdin);
// fclose(stdout);
return 0;
}
4. 洛谷 P4098 [HEOI2013] ALO
点击查看题面
给定一个长为 \(n\) 的数组 \(a\)，\(a\) 中的元素两两不同。
定义一个区间 \([l, r](l < r)\) 的权值为：在 \(a_l, a_{l + 1}, \cdots, a_r\) 这些数中，“任意一个数与次大值的异或和”的最大值。
请你选择一个区间 \([l, r](l < r)\)，最大化它的权值。只需给出这个权值即可。
\(1 \leq n \leq 5 \times 10^4\)，\(0 \leq a_i \leq 10^9\)。
点击查看题解
枚举次大值 \(a_i\)，考虑什么区间才能使这个值成为次大值。
从 \(a_i\) 出发向两边走，记两边走到的前两个比 \(a_i\) 大的值分别为 \(a_{l_1}, a_{l_2}\) 和 \(a_{r_1}, a_{r_2}(l_2 < l_1 < i < r_1 < r_2)\)。
容易发现，当区间左端点在 \((l_2, l_1]\) 中、右端点在 \([i, r_1)\) 中或左端点在 \((l_1, i]\) 中、右端点在 \([r_1, r_2)\) 中时，\(a_i\) 是这个区间的最大值。
而又发现一个性质：若区间 \([L_1, R_1]\) 包含区间 \([L_2, R_2]\) 且两区间的最大值相同，则选择区间 \([L_1, R_1]\) 一定不劣于选择区间 \([L_2, R_2]\)。因为后者次大值异或的数一定也属于前者。
因此对于枚举到的最大值 \(a_i\)，只需决策区间 \((l_2, r_1)\) 和 \((l_1, r_2)\) 到底哪个更优即可。
决策的部分是经典的最大异或和问题，可以用可持久化 Trie 解决。找到 \(l_1, l_2, r_1, r_2\) 可以在 st 表上二分。
时间复杂度为 \(\Theta(n(\log n + \log V))\)，其中 \(V\) 为值域。
点击查看代码
#include <cstdio>
#include <iostream>
using namespace std;
const int N=50003,M=30,log_N=17;
struct Trie{
int len_node=0,node[N*(M+2)][2],root[N];
void insert(int p,int q,int x){
p=root[p],q=root[q]=++len_node;
for(int i=M-1;i>=0;i--){
node[q][!(x>>i&1)]=node[p][!(x>>i&1)];
node[q][x>>i&1]=++len_node;
p=node[p][x>>i&1],q=node[q][x>>i&1];
}
}
int query(int l,int r,int x){
if(l>=r) return 0;
int i,ans=0;
l=root[l],r=root[r];
for(i=M-1;i>=0;i--)
if(node[r][!(x>>i&1)]==node[l][!(x>>i&1)])
l=node[l][x>>i&1],r=node[r][x>>i&1];
else
l=node[l][!(x>>i&1)],r=node[r][!(x>>i&1)],ans|=1<<i;
return ans;
}
}trie;
int n,a[N];
struct RMQ{
int st[log_N][N],lgt[N];
void build(){
for(int i=0;(1<<i)<=n;i++)
lgt[1<<i]=i;
for(int i=3;i<=n;i++)
if(lgt[i]==0) lgt[i]=lgt[i-1];
for(int i=1;i<=n;i++)
st[0][i]=a[i];
for(int i=1;i<log_N;i++)
for(int j=1;j+(1<<i)-1<=n;j++)
st[i][j]=max(st[i-1][j],st[i-1][j+(1<<i-1)]);
}
int query(int l,int r){
int d=lgt[r-l+1];
return max(st[d][l],st[d][r-(1<<d)+1]);
}
}rmq;
int binary1(int r,int x,int br){
int l=0,mid;
while(l<r){
mid=(l+r+1)/2;
if(rmq.query(mid,br)>=x) l=mid;
else r=mid-1;
}
return l;
}
int binary2(int l,int x,int bl){
int r=n+1,mid;
while(l<r){
mid=(l+r)/2;
if(rmq.query(bl,mid)>=x) r=mid;
else l=mid+1;
}
return r;
}
int main(){
// freopen("ALO.in","r",stdin);
// freopen("ALO.out","w",stdout);
int i,s1,s2,s3,ans=0;
scanf("%d",&n);
for(i=1;i<=n;i++){
scanf("%d",&a[i]);
trie.insert(i-1,i,a[i]);
}
rmq.build();
for(i=1;i<=n;i++){
s1=binary1(i-1,a[i],i-1);
s2=binary2(i+1,a[i],i+1);
if(s1>0){
s3=binary1(s1-1,a[i],s1-1);
ans=max(ans,trie.query(s3,s2-1,a[i]));
}
if(s2<=n){
s3=binary2(s2+1,a[i],s2+1);
ans=max(ans,trie.query(s1,s3-1,a[i]));
}
}
printf("%d",ans);
// fclose(stdin);
// fclose(stdout);
return 0;
}
5. AGC044C Strange Dance
点击查看题面
有 \(3^n\) 个人围成一圈跳舞。我们从任意一个位置开始，将所有位置标号为 \(0 \sim 3^n - 1\)。
初始时，编号为 \(i\) 的人站在编号为 \(i\) 的位置上。
他们会跳 \(q\) 支舞。跳的每支舞都是以下两种类型之一：
- Salsa 舞。此时位置 \(i\) 上的人走向位置 \(j\) 当且仅当 \(i\) 和 \(j\) 的三进制表示中，\(i\) 为 \(0\) 的位置上 \(j\) 为 \(0\)，\(i\) 为 \(1\) 的位置上 \(j\) 为 \(2\)，\(i\) 为 \(2\) 的位置上 \(j\) 为 \(1\)。
- Rumba 舞。此时位置 \(i\) 上的人走向位置 \((i + 1) \bmod 3^n\)。
给定这 \(q\) 支舞的类型，对于每个 \(i \in [0, 3^n)\)，求出编号为 \(i\) 的人最终会站在哪个位置上。
\(1 \leq n \leq 12\)，\(1 \leq q \leq 2 \times 10^5\)。
点击查看题解
时刻注意题目中说的是“位置”的编号还是“人”的编号。
我们用 Trie 维护当前位置 \(i\) 上站的是哪个人。即在 0-1-2 Trie 上匹配数 \(i\)，在最终跳到结点上打个标记 \(\mathrm{num}\)，\(\mathrm{num}\) 的值表示位置 \(i\) 上站着的人的编号。
我们看看跳每支舞时 Trie 的形态会发生什么变化。
- Salsa 舞。相当于对于每个结点 \(u\)，交换 \(u\) 的 \(1\) 儿子和 \(2\) 儿子（想想是不是这样）。
- Rumba 舞。相当于对 Trie 维护的每个值（即位置编号）加 \(1\)。
对于第一种操作，容易使用懒标记维护。
对于第二种操作，Trie 也能维护全局加 \(1\)。由于加 \(1\) 操作是从最低位开始的，因此我们需要从低位到高位插入每个数。
每次加 \(1\) 时，我们发现：
- 以 \(0\) 结尾和以 \(1\) 结尾的数，只需在最低位加 \(1\)，其他位保持不变。
- 以 \(2\) 结尾的数，需要将最低位变成 \(0\)，然后在次低位上加 \(1\)，继续如上讨论。
对应到 Trie 上即为：先将 \(u\) 的 \(0\) 儿子变成 \(1\) 儿子，\(1\) 儿子变成 \(2\) 儿子，\(2\) 儿子变成 \(0\) 儿子，再递归到 \(0\) 儿子继续处理。
这样，我们就能在 \(\Theta(\log V)\) 的时间复杂度内完成全局加 \(1\) 的操作（其中 \(V\) 为值域，即 \(V = 3^n\))。
总时间复杂度为 \(\Theta(nq)\)。
点击查看代码
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int N=(int)6e5+3,M=12,P=(int)2e5+3;
int pow3[M+3],n,m,pos[N*M],ans[N];
char a[P];
void init_pow3(){
pow3[0]=1;
for(int i=1;i<=M;i++)
pow3[i]=pow3[i-1]*3;
}
struct Trie{
struct Node{
bool rev;
int ne[3];
}node[N*M];
// A node denotes a position, NOT a person.
int len_node;
void init_Trie(){
len_node=1;
node[1]={0,{0,0}};
}
int make_node(){
int u=++len_node;
node[u]={0,{0,0}};
return u;
}
void update(int u){
if(u==0) return ;
swap(node[u].ne[1],node[u].ne[2]);
node[u].rev^=1;
}
void push_down(int u){
if(u==0) return ;
if(!node[u].rev) return ;
update(node[u].ne[0]);
update(node[u].ne[1]);
update(node[u].ne[2]);
node[u].rev=0;
}
int insert(int x){
// Insert elements only at the beginning.
int cur=1,i;
for(i=0;i<n;i++){
if(node[cur].ne[x/pow3[i]%3]==0)
node[cur].ne[x/pow3[i]%3]=make_node();
cur=node[cur].ne[x/pow3[i]%3];
}
return cur;
}
void modify(){
// Add 1 to every element.
int cur=1,i;
for(i=0;i<n;i++){
push_down(cur);
swap(node[cur].ne[0],node[cur].ne[1]);
swap(node[cur].ne[0],node[cur].ne[2]);
cur=node[cur].ne[0];
}
}
int query(int x){
int cur=1,i;
for(i=0;i<n;i++){
push_down(cur);
cur=node[cur].ne[x/pow3[i]%3];
}
return cur;
}
}trie;
int main(){
// freopen("dance.in","r",stdin);
// freopen("dance.out","w",stdout);
int i;
init_pow3();
trie.init_Trie();
scanf("%d%s",&n,&a[1]);
m=strlen(&a[1]);
for(i=0;i<pow3[n];i++)
pos[trie.insert(i)]=i;
for(i=1;i<=m;i++)
switch(a[i]){
case 'S': trie.update(1); break;
case 'R': trie.modify();
}
for(i=0;i<pow3[n];i++)
ans[pos[trie.query(i)]]=i;
for(i=0;i<pow3[n];i++)
printf("%d ",ans[i]);
// fclose(stdin);
// fclose(stdout);
return 0;
}
6. 洛谷 P6623 [省选联考 2020 A 卷] 树
点击查看题面
给定一棵 \(n\) 个结点的有根树 \(T\)，结点从 \(1\) 开始编号，根结点为 \(1\) 号结点，每个结点有一个正整数权值 \(v_i\)。
设 \(x\) 号结点的子树内（包含 \(x\) 自身）的所有结点编号为 \(c_1,c_2,\dots,c_k\)，定义 \(x\) 的价值为：
其中 \(d(x, y)\) 表示树上 \(x\) 号结点与 \(y\) 号结点间唯一简单路径所包含的边数，\(d(x, x) = 0\)。\(\oplus\) 表示异或运算。
请你求出 \(\sum_{i = 1}^n \operatorname{val}(i)\) 的结果。
\(1 \leq n, v_i \leq 525010\)，\(1 \leq p_i \leq n\)。
点击查看题解
定义 \(S_x\) 表示对 \(x\) 子树中的所有点 \(u\)，\(v_u + d(u, x)\) 的值构成的集合。
要求的 \(\operatorname{val}(x)\) 即为 \(S_x\) 中所有值的异或和。
对整棵树从下往上考虑。考虑对于结点 \(x\)，若已知 \(x\) 的所有子结点 \(u\) 的 \(S_u\)，如何求出 \(S_x\)。
事实上我们只需要干如下三件事：
- 对 \(x\) 的所有儿子 \(u\)，将 \(S_u\) 的所有值加 \(1\)。
- 对 \(x\) 的儿子 \(u\)，合并所有 \(S_u\)。记合并后的集合为 \(T\)。
- 在 \(T\) 中插入 \(v_x\)，得到 \(S_x\)。
所有修改和查询操作容易用 Trie 维护。
全局加 \(1\) 的操作仿照上一题完成，只需从低位到高位插入每个数，并在修改时从根节点开始执行：
- 记当前结点为 \(u\)，交换 \(u\) 的 \(0\) 儿子和 \(1\) 儿子。
- 递归到 \(0\) 儿子重复以上操作。
时间复杂度为 \(\Theta(n \cdot \log V)\)，其中 \(V\) 为值域。
点击查看代码
#include <cstdio>
#include <cstring>
#include <iostream>
#include <stack>
using namespace std;
const int N=530003,M=21;
struct Trie{
struct Node{
int ne[2],d,cnt,sum;
}node[N*(M+2)];
int len_node=0;
int make_node(int d){
int u=++len_node;
node[u]={{0,0},d,0,0};
return u;
}
void push_up(int u){
if(u==0) return ;
if(node[u].d==M-1) return ;
int l=node[u].ne[0],r=node[u].ne[1];
node[u].cnt=node[l].cnt+node[r].cnt;
node[u].sum=node[l].sum^node[r].sum;
if(node[r].cnt&1) node[u].sum|=1<<node[u].d+1;
}
int merge(int u,int v){
if(u==0||v==0) return max(u,v);
node[u].cnt+=node[v].cnt;
node[u].sum^=node[v].sum;
node[u].ne[0]=merge(node[u].ne[0],node[v].ne[0]);
node[u].ne[1]=merge(node[u].ne[1],node[v].ne[1]);
return u;
}
void insert(int u,int x){
stack<int> ned;
for(int i=0;i<M;i++){
ned.push(u);
if(node[u].ne[x>>i&1]==0)
node[u].ne[x>>i&1]=make_node(i);
u=node[u].ne[x>>i&1];
}
node[u].cnt++;
while(!ned.empty())
push_up(ned.top()),ned.pop();
}
void modify(int u){
// Add 1 to every element of subtree #u.
stack<int> ned;
for(int i=0;i<M&&u>0;i++){
swap(node[u].ne[0],node[u].ne[1]);
ned.push(u); u=node[u].ne[0];
}
while(!ned.empty())
push_up(ned.top()),ned.pop();
}
int query(int u){
return node[u].sum;
}
}trie;
int n,a[N],root[N];
int len_list=0,e[N],ne[N],h[N];
long long ans=0;
void add_once(int a,int b){
e[len_list]=b;
ne[len_list]=h[a];
h[a]=len_list++;
}
void dfs(int u){
for(int i=h[u];i>=0;i=ne[i]) dfs(e[i]);
root[u]=trie.make_node(-1);
trie.insert(root[u],a[u]);
for(int i=h[u];i>=0;i=ne[i]){
trie.modify(root[e[i]]);
root[u]=trie.merge(root[u],root[e[i]]);
}
ans+=trie.query(root[u]);
}
int main(){
// freopen("tree.in","r",stdin);
// freopen("tree.out","w",stdout);
int i,x;
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
memset(h,-1,sizeof h);
for(i=2;i<=n;i++){
scanf("%d",&x);
add_once(x,i);
}
dfs(1);
printf("%lld",ans);
// fclose(stdin);
// fclose(stdout);
return 0;
}
7. HDU7526 cats 的集合 1
点击查看题面
有一个可重集 \(S\)。开始时，可重集中存在 \(n\) 个元素 \(p_1, p_2, \cdots, p_n\)。
给定 \(m\) 次操作。操作分为以下 \(5\) 种：
- \(1~a\)：在可重集中加入元素 \(a\)。
- \(2~a\)：将可重集中的每个元素都变为其与 \(a\) 按位或运算的结果。
- \(3~a\)：将可重集中的每个元素都变为其与 \(a\) 按位与运算的结果。
- \(4~a\)：将可重集中的每个元素都变为其与 \(a\) 按位异或运算的结果。
- \(5~a\)：查询可重集中每一个元素与 \(a\) 按位异或运算结果中的最大值。
多组测试数据。
\(1 \leq n, m \leq 2 \times 10^5\)，\(1 \leq \sum n, \sum m \leq 1.5 \times 10^6\)，\(0 \leq a < 2^{31}\)。
点击查看题解
使用 Trie 维护 \(a\) 中的元素。从高位到低位插入每个元素。
考虑维护两个标记 \(\mathrm{v_{xor}}\) 和 \(\mathrm{v_{or}}\)，表示当前 Trie 内的值 \(x\)，\(((x \vee \mathrm{v_{or}}) \oplus \mathrm{v_{xor}})\) 才是其真实维护的值。
- 对于异或运算：只需令 \(\mathrm{v_{xor}} \leftarrow \mathrm{v_{xor}} \oplus a\)。
- 对于或运算：只需令 \(\mathrm{v_{or}} \leftarrow \mathrm{v_{or}} \vee x\)，\(\mathrm{v_{xor}} \leftarrow \mathrm{v_{xor}} \vee \urcorner x\)。
- 对于与运算：只需令 \(\mathrm{v_{or}} \leftarrow \mathrm{v_{or}} \vee \urcorner x\)，\(\mathrm{v_{xor}} \leftarrow \mathrm{v_{xor}} \vee \urcorner x\)。
若无插入操作，只需将这两个标记在全局永久化，即可做到 \(\Theta(n \log n)\)。
现在有插入操作，每次插入一个数可能导致懒标记 \(\mathrm{v_{or}}\) 失效。因此，我们必须将懒标记下放到每个结点上。
然而在 push down 懒标记的时候可能会进行很多次 merge 操作。乍一看去，时间复杂度无法接受。
但我们发现插入最多只会插入 \(\Theta((n + m)\log V)\) 次，而 merge 函数每次递归必然会删去一个结点。也就是说，在有插入操作的情况下，边 push down 边 merge 的复杂度仍然可以接受，为 \(\Theta((n + m)\log V)\)。
因此，无需担心时间复杂度，只需将上面维护的标记作为懒标记正常下放即可。
时间复杂度为 \(\Theta((n + m)\log V)\)，其中 \(V\) 为值域。
点击查看代码
#include <cstdio>
#include <iostream>
using namespace std;
const int N=400003,M=31;
int max(int a,int b){
return (a>b)?a:b;
}
struct Trie{
struct Node{
int ne[2],d;
unsigned v_xor,v_or;
// d: depth (d[leaf] = 0, d[father] = d[son] + 1).
// v_xor, v_or: value in [0, 2^d).
}node[N*M];
int len_node=0;
void clear(){
len_node=1;
node[1]={{0,0},M,0,0};
}
int make_node(int d){
int u=++len_node;
node[u]={{0,0},d,0,0};
return u;
}
void push_down(int u){
int l,r;
if(u==0) return ;
if(node[u].d==0) return ;
// push down v_or
if(node[u].v_or>>(node[u].d-1)&1){
node[u].ne[1]=merge(node[u].ne[0],node[u].ne[1]);
node[u].v_or^=1u<<(node[u].d-1);
node[u].ne[0]=0;
}
l=node[u].ne[0],r=node[u].ne[1];
node[l].v_or|=node[u].v_or;
node[r].v_or|=node[u].v_or;
node[l].v_xor&=~node[u].v_or;
node[r].v_xor&=~node[u].v_or;
node[u].v_or=0;
// push down v_xor
if(node[u].v_xor>>(node[u].d-1)&1){
swap(node[u].ne[0],node[u].ne[1]);
node[u].v_xor^=1u<<(node[u].d-1);
}
l=node[u].ne[0],r=node[u].ne[1];
node[l].v_xor^=node[u].v_xor;
node[r].v_xor^=node[u].v_xor;
node[u].v_xor=0;
}
int merge(int u,int v){
if(u==0||v==0) return max(u,v);
push_down(u),push_down(v);
node[u].ne[0]=merge(node[u].ne[0],node[v].ne[0]);
node[u].ne[1]=merge(node[u].ne[1],node[v].ne[1]);
return u;
}
void insert(unsigned x){
int cur=1,i;
for(i=M-1;i>=0;i--){
push_down(cur);
if(node[cur].ne[x>>i&1]==0)
node[cur].ne[x>>i&1]=make_node(i);
cur=node[cur].ne[x>>i&1];
}
}
void modify_xor(unsigned x){
node[1].v_xor^=x;
}
void modify_or(unsigned x){
node[1].v_or|=x;
node[1].v_xor&=~x;
}
void modify_and(unsigned x){
node[1].v_or|=~x;
node[1].v_xor|=~x;
}
unsigned query(unsigned x){
int cur=1,i;
unsigned ans=0;
for(i=M-1;i>=0;i--){
push_down(cur);
if(node[cur].ne[!(x>>i&1)]>0)
cur=node[cur].ne[!(x>>i&1)],ans|=1u<<i;
else cur=node[cur].ne[x>>i&1];
}
return ans;
}
}trie;
int main(){
// freopen("trie.in","r",stdin);
// freopen("trie.out","w",stdout);
int i,n,m,opt,t;
unsigned x;
for(scanf("%d",&t);t>0;t--){
scanf("%d%d",&n,&m);
trie.clear();
for(i=1;i<=n;i++){
scanf("%u",&x);
trie.insert(x);
}
for(i=1;i<=m;i++){
scanf("%d%u",&opt,&x);
switch(opt){
case 1: trie.insert(x); break;
case 2: trie.modify_or(x); break;
case 3: trie.modify_and(x); break;
case 4: trie.modify_xor(x); break;
case 5: printf("%u\n",trie.query(x));
}
}
}
// fclose(stdin);
// fclose(stdout);
return 0;
}
8. LOJ6144「2017 山东三轮集训 Day6」C
点击查看题面
给定一个长为 \(n\) 的序列 \(a\)。
给定 \(m\) 次操作，每次操作为以下 \(4\) 中类型之一：
- \(\texttt{Xor x}\)：将序列 \(a\) 中的每个数都按位异或上 \(x\)。
- \(\texttt{And x}\)：将序列 \(a\) 中的每个数都按位与上 \(x\)。
- \(\texttt{Or x}\)：将序列 \(a\) 中的每个数都按位或上 \(x\)。
- \(\texttt{Ask l r k}\)：询问 \(a\) 中下标在 \([l, r]\) 的数中第 \(k\) 小的数是多少。
保证操作一定合法，询问的答案一定存在。
\(1 \leq n \leq 5 \times 10^4\)，\(0 \leq a_i, x < 2^{31}\)。
点击查看题解
修改操作与上一题类似。但注意到查询的下标是一个区间，因此我们需要开可持久化 Trie。
而可持久化 Trie 难以维护懒标记。但注意到这道题没有插入操作，因此我们考虑在全局维护标记 \(\mathrm{v_{xor}}\) 和 \(\mathrm{v_{or}}\)。
维护 \(\mathrm{v_{xor}}\) 是容易的。但若维护 \(\mathrm{v_{or}}\)，在查询操作遍历到某一个 \(\mathrm{v_{or}}\) 值为 \(1\) 的位时（假设当前结点的两个儿子都存在），由于我们无法快速确定第 \(k\) 小的数在 \(0\) 和 \(1\) 哪个儿子中（或上 \(\mathrm{v_{or}}\) 后都为 \(1\)），因此两个儿子都要递归。这样一来，单次询问的时间复杂度就变成 \(\Theta(n \cdot \log V)\)，难以接受。
我们发现上述算法的时间复杂度瓶颈在于：有查询操作，\(\mathrm{v_{or}}\) 的某一位为 \(1\)，Trie 树对应层（位）的某个结点上两个儿子都存在。当这三个条件同时满足，时间复杂度就会爆炸。
因此我们考虑，一旦出现这种情况，就暴力重构整颗可持久化 Trie。由于每次重构必然会使得 Trie 树的某一层上只有左儿子或右儿子（原来两个儿子都有，且无插入操作），因此这种重构只会进行 \(\Theta(\log V)\) 次。
因此总时间复杂度为 \(\Theta(n \cdot \log^2 V)\)，瓶颈在于重构。
实现时需要在全局多维护一个信息 \(\mathrm{has}(0 / 1, i)(i \in [0, \log V))\)，表示树上的第 \(i\) 层是否有结点存在左 / 右儿子（压成二进制数维护）。
点击查看代码
#include <cstdio>
const int N=50003,M=31;
int n; unsigned a[N];
struct Trie{
struct Node{
int ne[2],d,cnt;
// d: depth(d[leaf] = 0, d[father] = d[son] + 1).
}node[N*(M+2)];
int len_node=0,root[N];
unsigned v_or,v_xor,has;
void clear(){
len_node=1,v_or=has=0;
node[1]={{0,0},M,0};
node[0]={{0,0},-1,0};
}
int make_node(int d){
int u=++len_node;
node[u]={{0,0},d,0};
return u;
}
void insert(int p,int q,unsigned x){
// Insert elements only when "v_or = 0".
p=root[p],q=root[q]=make_node(M);
node[q].cnt=node[p].cnt+1;
for(int i=M-1;i>=0;i--){
if(!(x>>i&1)) has|=1u<<i;
node[q].ne[!(x>>i&1)]=node[p].ne[!(x>>i&1)];
node[q].ne[x>>i&1]=make_node(i);
p=node[p].ne[x>>i&1],q=node[q].ne[x>>i&1];
node[q].cnt=node[p].cnt+1;
}
}
void rebuild(){
for(int i=1;i<=n;i++)
a[i]|=v_or;
clear();
for(int i=1;i<=n;i++)
insert(i-1,i,a[i]);
}
void modify_xor(unsigned x){
v_xor^=x;
}
void modify_or(unsigned x){
v_or|=x,v_xor&=~x;
}
void modify_and(unsigned x){
v_or|=~x,v_xor|=~x;
}
unsigned query(int l,int r,int k){
if((has&v_or)>0) rebuild();
int i,s1,s2,s3; unsigned ans=0;
l=root[l],r=root[r];
for(i=M-1;i>=0;i--){
s1=node[r].ne[v_xor>>i&1];
s2=node[l].ne[v_xor>>i&1];
s3=node[s1].cnt-node[s2].cnt;
if(s3>=k) l=s2,r=s1;
else{
k-=s3,ans|=1u<<i;
l=node[l].ne[!(v_xor>>i&1)];
r=node[r].ne[!(v_xor>>i&1)];
}
}
return ans;
}
}trie;
int main(){
// freopen("trie.in","r",stdin);
// freopen("trie.out","w",stdout);
char opt[6]; unsigned x;
int i,m,l,r,k;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
scanf("%u",&a[i]);
trie.clear();
for(i=1;i<=n;i++)
trie.insert(i-1,i,a[i]);
for(i=1;i<=m;i++){
scanf("%s",opt);
switch(opt[1]){
case 'o':
scanf("%u",&x);
trie.modify_xor(x);
break;
case 'n':
scanf("%u",&x);
trie.modify_and(x);
break;
case 'r':
scanf("%u",&x);
trie.modify_or(x);
break;
case 's':
scanf("%d%d%d",&l,&r,&k);
printf("%u\n",trie.query(l-1,r,k));
}
}
// fclose(stdin);
// fclose(stdout);
return 0;
}
9. CF1515H Phoenix and Bits
点击查看题面
有一个集合 \(a\)，初始时有 \(n\) 个数 \(a_1, a_2, \cdots, a_n\)。
现有 \(q\) 次操作，每次操作为以下 \(4\) 种类型之一：
- \(1~x~y~z\)：将大小在 \([x, y]\) 中的数按位与 \(z\)。
- \(2~x~y~z\)：将大小在 \([x, y]\) 中的数按位与 \(z\)。
- \(3~x~y~z\)：将大小在 \([x, y]\) 中的数按位与 \(z\)。
- \(4~x~y\)：查询大小在 \([x, y]\) 中的不同数的个数。
\(1 \leq n \leq 2 \times 10^5\)，\(1 \leq q \leq 10^5\)，\(0 \leq x, y, z < 2^20\)，\(x \leq y\)。
点击查看题解
操作与前两题类似，区别在于本题没有插入操作，且每个操作都是在一段值域上进行的。
因此考虑在每个结点上打上懒标记 \(\mathrm{v_{xor}}\) 和 \(\mathrm{v_{or}}\)，修改时将修改的部分分裂出去，打上懒标记，在合并回来。
但是注意到这道题维护的是“集合”而不是“可重集”，且询问有多少个不同的数。因此你在修改时可能会将两个数合并成一个数，这样做法就假掉了。
你可能会想，每次合并回来时在 merge 函数里特判一下不就好了吗。这对 xor 操作确实是成立的。但注意到对于 or 操作，即便每次修改是全局的，也有可能把两个数变得相同。而每次懒标记不一定会下放到叶节点，维护的答案“不同数的个数”无法及时更新，答案还是有可能是错的。
我们发现懒标记 \(\mathrm{v_{or}}\) 难以维护。因此我们考虑一个更加暴力的思路，直接放弃维护 \(\mathrm{v_{or}}\)，而是每次想要进行 or 操作的时候都暴力递归到子树中合并结点。
直接这么合并肯定会 TLE，但我们加上一个剪枝：只有在当前子树中存在需要合并的结点时才递归合并。即若只存在将某些左儿子变成右儿子、右儿子变成左儿子的操作，不存在将两个节点合并成一个的操作，则停止递归。
具体地，跟上一题一样，考虑在每个节点上维护 \(\mathrm{has}(0 / 1)\)，表示当前结点上有左 / 右儿子的层有哪些（压成二进制数维护）。只有当存在某一位，要“按位或”的值在这一位是 \(1\)，且这一位左右儿子都存在时，我们才认为这棵子树需要合并。
对于不需要合并、只需改变某些左右儿子状态的子树，直接将“或标记”变成“异或标记”即可。
为什么加上剪枝后时间复杂度就是对的呢？
我们令 \(t\) 表示对于每个结点，它需要合并的二进制位（即这一位要或上的数为 \(1\)，且左、右儿子同时存在）的数量之和。
发现每次递归必然会导致某个结点的某个二进制位合并，由于没有插入操作，之后这个结点的这个二进制位必然不会再合并。即，每次递归必然会使 \(t\) 减 \(1\)。
而我们发现总结点数在任何时刻都不超过 \(\Theta(n \cdot \log V)\)。因此，\(t\) 的初值不超过 \(\Theta(n \cdot \log^2 V)\)，即最多只会递归 \(\Theta(n \cdot \log^2 V)\) 次。
因此，合并的时间复杂度即为 \(\Theta(n \cdot \log^2 V)\)，可以接受。
总时间复杂度为 \(\Theta(n \cdot \log^2 V + q \cdot \log V)\)。
点击查看代码
#include <cstdio>
#include <iostream>
#include <stack>
using namespace std;
const int N=200003,M=20,P=N*(M+2);
struct Trie{
struct Node{
int ne[2],d,cnt;
unsigned val,has[2];
// d: depth(d[leaf] = 0, d[father] = d[son] + 1)
// val: the value in [0, 2^d) needing xor-ing.
// has[i]: the digits whose bits contain i(i in {0, 1}).
}node[P];
int root; stack<int> rcy;
void init_Trie(){
root=1,node[1]={{0,0},M,0,0,{0,0}};
for(int i=P-1;i>1;i--)
rcy.push(i);
}
int make_node(int d){
int u=rcy.top(); rcy.pop();
node[u]={{0,0},d,0,0,{0,0}};
return u;
}
void update(int u,unsigned x){
if(u==0) return ;
if(node[u].d==0) return ;
if(x>>(node[u].d-1)&1)
swap(node[u].ne[0],node[u].ne[1]);
node[u].val^=x&((1u<<(node[u].d-1))-1);
int s0=node[u].has[0]&x;
int s1=node[u].has[1]&x;
node[u].has[0]=(node[u].has[0]&~x)|s1;
node[u].has[1]=(node[u].has[1]&~x)|s0;
}
void push_up(int u){
if(u==0) return ;
if(node[u].d==0) return ;
int l=node[u].ne[0],r=node[u].ne[1];
node[u].cnt=node[l].cnt+node[r].cnt;
node[u].has[0]=node[l].has[0]|node[r].has[0];
node[u].has[1]=node[l].has[1]|node[r].has[1];
if(l>0) node[u].has[0]|=1u<<(node[u].d-1);
if(r>0) node[u].has[1]|=1u<<(node[u].d-1);
}
void push_down(int u){
if(u==0) return ;
if(node[u].d==0) return ;
update(node[u].ne[0],node[u].val);
update(node[u].ne[1],node[u].val);
node[u].val=0;
}
void split(int u,unsigned x,int& root1,int& root2){
if(x>=(1u<<M)){
root1=u,root2=0;
return ;
}
if(u==0||node[u].d==0){
root1=0,root2=u;
return ;
}
int v=make_node(node[u].d);
push_down(u);
if(x>>(node[u].d-1)&1){
root1=u,root2=v;
split(node[u].ne[1],x,node[u].ne[1],node[v].ne[1]);
}
else{
root1=v,root2=u;
split(node[u].ne[0],x,node[v].ne[0],node[u].ne[0]);
}
push_up(u),push_up(v);
if(node[root1].cnt==0)
rcy.push(root1),root1=0;
if(node[root2].cnt==0)
rcy.push(root2),root2=0;
}
int merge(int u,int v){
if(u==0||v==0) return max(u,v);
if(node[u].d==0){
node[u].cnt=1,rcy.push(v);
return u;
}
push_down(u),push_down(v);
node[u].ne[0]=merge(node[u].ne[0],node[v].ne[0]);
node[u].ne[1]=merge(node[u].ne[1],node[v].ne[1]);
push_up(u),rcy.push(v); return u;
}
void update_or(int u,unsigned x){
if(u==0) return ;
if(node[u].d==0) return ;
if(((node[u].has[0]^node[u].has[1])&x)==x){
update(u,node[u].has[0]&x);
return ;
}
push_down(u);
if(x>>(node[u].d-1)&1){
node[u].ne[1]=merge(node[u].ne[0],node[u].ne[1]);
x&=(1u<<(node[u].d-1))-1,node[u].ne[0]=0;
}
update_or(node[u].ne[0],x);
update_or(node[u].ne[1],x);
push_up(u);
}
void insert(unsigned x){
// Insert elements only at the beginning.
int cur=root,i;
stack<int> ned;
for(i=M-1;i>=0;i--){
ned.push(cur);
if(node[cur].ne[x>>i&1]==0)
node[cur].ne[x>>i&1]=make_node(i);
cur=node[cur].ne[x>>i&1];
}
node[cur].cnt=1;
while(!ned.empty())
push_up(ned.top()),ned.pop();
}
void modify_xor(unsigned l,unsigned r,unsigned x){
int u1,u2,u3;
split(root,l,u1,u3);
split(u3,r+1,u2,u3);
update(u2,x);
root=merge(u1,merge(u2,u3));
}
void modify_or(unsigned l,unsigned r,unsigned x){
int u1,u2,u3;
split(root,l,u1,u3);
split(u3,r+1,u2,u3);
update_or(u2,x);
root=merge(u1,merge(u2,u3));
}
void modify_and(unsigned l,unsigned r,unsigned x){
int u1,u2,u3;
split(root,l,u1,u3);
split(u3,r+1,u2,u3);
update_or(u2,(~x)&((1u<<M)-1));
update(u2,(~x)&((1u<<M)-1));
root=merge(u1,merge(u2,u3));
}
int query(unsigned l,unsigned r){
int u1,u2,u3,ans;
split(root,l,u1,u3);
split(u3,r+1,u2,u3);
ans=node[u2].cnt;
root=merge(u1,merge(u2,u3));
return ans;
}
}trie;
int main(){
// freopen("bit.in","r",stdin);
// freopen("bit.out","w",stdout);
int i,n,q,opt,l,r; unsigned x;
scanf("%d%d",&n,&q);
trie.init_Trie();
for(i=1;i<=n;i++){
scanf("%u",&x);
trie.insert(x);
}
for(i=1;i<=q;i++){
scanf("%d%d%d",&opt,&l,&r);
switch(opt){
case 1:
scanf("%u",&x);
trie.modify_and(l,r,x);
break;
case 2:
scanf("%u",&x);
trie.modify_or(l,r,x);
break;
case 3:
scanf("%u",&x);
trie.modify_xor(l,r,x);
break;
case 4:
printf("%d\n",trie.query(l,r));
}
}
// fclose(stdin);
// fclose(stdout);
return 0;
}
10. 洛谷 P6018 [Ynoi2010] Fusion tree
点击查看题面
给定一棵 \(n\) 个结点的树，初始时第 \(i\) 个结点的权值为 \(a_i\)。
给定 \(m\) 次操作，每次操作为以下 \(3\) 种之一：
- \(1~x\)：将所有与 \(x\) 相邻的结点（不包括 \(x\)）的点权加 \(1\)。
- \(2~x~v\)：将结点 \(x\) 的点权减 \(v\)。
- \(3~x\)：询问所有与 \(x\) 相邻的结点（不包括 \(x\)）的点权的异或和。
\(1 \leq n, m \leq 5 \times 10^5\)，\(0 \leq a_i \leq 10^5\)，保证点权任意时刻为非负整数。
点击查看题解
发现与 \(x\) 相邻的结点相当于 \(x\) 的所有儿子，加上 \(x\) 的父亲。
因此修改时，我们考虑在父亲处维护儿子的懒标记。即在结点 \(u\) 除维护懒标记 \(b_u\)，表示 \(u\) 每个子结点维护的 \(a_v\) 要加上 \(b_u\) 才是真实的权值。特别的，我们规定 \(1\) 的父亲为 \(0\)（即 \(1\) 的懒标记在 \(0\) 处维护）。
对于 \(1\) 操作，我们只需要将 \(b_x, a_{\operatorname{fa}(x)}\) 加 \(1\)，其中 \(\operatorname{fa}(x)\) 表示 \(x\) 的父亲；对于 \(2\) 操作，只需要将 \(a_x\) 减 \(v\)。
对于 \(3\) 操作，我们使用 Trie 来快速地维护所有点的异或和。因此在 \(1\) 和 \(2\) 操作中，我们还需要支持 Trie 上单点修改和全局加 \(1\) 的操作。
单点修改只需要将原来的数删除，然后插入新的数即可。全局加 \(1\) 可以模仿 AGC044C Strange Dance 那道题，从低位到高位存储每个数，并递归处理。
时间复杂度为 \(\Theta(n \log V)\)，其中 \(V\) 为值域。
点击查看代码
#include <cstdio>
#include <cstring>
#include <iostream>
#include <stack>
using namespace std;
const int N=500003,M=20;
struct Trie{
struct Node{
int ne[2],d,cnt,sum;
}node[N*2*M];
int len_node=0;
int make_node(int d){
int u=++len_node;
node[u]={{0,0},d,0,0};
return u;
}
void push_up(int u){
if(u==0||node[u].d==M-1) return ;
int l=node[u].ne[0],r=node[u].ne[1];
node[u].cnt=node[l].cnt+node[r].cnt;
node[u].sum=node[l].sum^node[r].sum;
if(node[r].cnt&1) node[u].sum|=1<<node[u].d+1;
}
void insert(int u,int x){
stack<int> ned;
for(int i=0;i<M;i++){
ned.push(u);
if(node[u].ne[x>>i&1]==0)
node[u].ne[x>>i&1]=make_node(i);
u=node[u].ne[x>>i&1];
}
node[u].cnt++;
while(!ned.empty())
push_up(ned.top()),ned.pop();
}
void erase(int u,int x){
stack<int> ned;
for(int i=0;i<M;i++){
ned.push(u);
u=node[u].ne[x>>i&1];
}
node[u].cnt--;
while(!ned.empty())
push_up(ned.top()),ned.pop();
}
void modify(int u){
// Add 1 to every element of subtree #u.
stack<int> ned;
for(int i=0;i<M&&u>0;i++){
swap(node[u].ne[0],node[u].ne[1]);
ned.push(u),u=node[u].ne[0];
}
while(!ned.empty())
push_up(ned.top()),ned.pop();
}
int query(int u){
return node[u].sum;
}
}trie;
int n,m,a[N],b[N],root[N],fa[N];
int len_list=0,e[N*2],ne[N*2],h[N];
void add_once(int a,int b){
e[len_list]=b;
ne[len_list]=h[a];
h[a]=len_list++;
}
void add_twice(int a,int b){
add_once(a,b);
add_once(b,a);
}
void dfs(int u,int father){
fa[u]=father;
trie.insert(root[fa[u]],a[u]);
root[u]=trie.make_node(-1);
for(int i=h[u];i>=0;i=ne[i])
if(e[i]!=fa[u]) dfs(e[i],u);
}
int main(){
// freopen("Fusion.in","r",stdin);
// freopen("Fusion.out","w",stdout);
int i,x,y,opt;
scanf("%d%d",&n,&m);
memset(h,-1,sizeof h);
for(i=1;i<n;i++){
scanf("%d%d",&x,&y);
add_twice(x,y);
}
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
root[0]=trie.make_node(-1);
dfs(1,0);
for(i=1;i<=m;i++){
scanf("%d%d",&opt,&x);
switch(opt){
case 1:
b[x]++,trie.modify(root[x]);
if(x>1){
trie.erase(root[fa[fa[x]]],a[fa[x]]+b[fa[fa[x]]]);
trie.insert(root[fa[fa[x]]],a[fa[x]]+b[fa[fa[x]]]+1);
a[fa[x]]++;
}
break;
case 2:
scanf("%d",&y);
trie.erase(root[fa[x]],a[x]+b[fa[x]]);
trie.insert(root[fa[x]],a[x]+b[fa[x]]-y);
a[x]-=y; break;
case 3:
y=trie.query(root[x]);
if(x>1) y^=a[fa[x]]+b[fa[fa[x]]];
printf("%d\n",y);
}
}
// fclose(stdin);
// fclose(stdout);
return 0;
}
11. 洛谷 P5312 [Ynoi2011] 竞赛实验班
点击查看题面
有一个长度为 \(n\) 的数组 \(a\)。下标从 \(1\) 开始标号。有 \(m\) 个操作需要处理，操作有如下四种：
- \(1~x\)：在数组 \(a\) 的末尾添加一个数 \(x\)。
- \(2~l~r\)：输出 \(\sum_{i = l}^{r} a_i\)。
- \(3~x\)：将数组 \(a\) 中的每个数 \(a_i\) 都改为 \(a_i \oplus x\)。（\(\oplus\) 表示异或操作）。
- \(4\)：将数组 \(a\) 从小到大排序。
\(1 \leq n, m \leq 10^5\), \(0 \leq x, a_i \leq 10^9\)。
点击查看题解
如果只有 \(3\) 操作，我们只需要维护一个全局标记 \(\mathrm{v_{xor}}\)，表示维护的每个数 \(a_i\) 异或上 \(\mathrm{v_{xor}}\) 才是真实的 \(a_i\)。
如果多了 \(1\) 操作，只需要在插入时将 \(x\) 异或上 \(\mathrm{v_{xor}}\) 再插入即可。
如果多了 \(2\) 操作，由于异或标记的存在，我们不好维护前缀和。但我们可以按位求和，在 \(\Theta(\log V)\) 的复杂度内解决问题。维护 \(\mathrm{has}(i, 0 / 1)\)，表示不考虑异或标记，序列中第 \(i\) 位 \(0 / 1\) 的个数。
容易再每次插入时 \(\Theta(\log V)\) 修改该数组。查询，令 \(s_i\) 为 \(\mathrm{v_{xor}}\) 的第 \(i\) 位，只需求出 \(\mathrm{has}(i, s_i) \times 2^i\) 的和。
如果存在 \(4\) 操作，我们考虑如何维护排序操作。
我们发现 Trie 中的数天然满足升序的性质。因此，排序时我们可以将序列中的所有数都丢进 Trie 内排序，并清空序列。
但我们发现异或操作可能改变 Trie 内部数的相对顺序，这是不可接受的。为保证时间复杂度，我们不能将 Trie 内的数重新移出来异或。
事实上，我们可以像 Trie 外的序列一样，在全局维护懒标记 \(\mathrm{v_{xor}}\)。每次需要排序的时候，我们只需将 \(\mathrm{v_{xor}}\) push down 到结点上即可（并将全局的 \(\mathrm{v_{xor}}\) 清零）。
Trie 内对 \(1\) 操作和 \(3\) 操作的维护与序列上的维护相同。
对于 \(2\) 操作，我们可以使用前缀和变成 \(\sum_{i = 1}^{r} a_i - \sum_{i = 1}^{l - 1} a_i\)。
对于 \(\sum_{i = 1}^{k} a_i\) 的查询，我们在每个结点上记录 \(\mathrm{cnt}\) 表示当前子树维护的数的个数，记录 \(\mathrm{has}(i, 0 / 1)\) 表示当前结点维护的所有数中第 \(i\) 位 \(0 / 1\) 的数量。
查询时先找出第 \(\mathrm{cnt}\) 大的数对应的链。然后对于链上每个结点的左子树都按位 \(\Theta(\log V)\) 地求一遍这个子树中所有数的和。
最后别忘了加上这条链对应的数。
因此，本题只需维护 Trie 和一个序列，加入时只在序列中加入；排序时将 Trie 的懒标记 \(\mathrm{v_{xor}}\) 下放，并将序列中的所有数（异或 \(\mathrm{v_{xor}}\) 后）丢进 Trie 中；查询时在 Trie 和序列上同时查询即可。
时间复杂度为 \(\Theta(n \log^2 V)\)。
点击查看代码
#include <cstdio>
#include <iostream>
#include <stack>
using namespace std;
const int N=200003,M=30;
struct Trie{
struct Node{
int ne[2],d,v_xor,cnt;
int has[M][2];
}node[N*M];
int len_node,v_xor;
void init_Trie(){
len_node=1,v_xor=0;
node[1]={{0,0},M,0,0,{}};
}
int make_node(int d){
int u=++len_node;
node[u]={{0,0},d,0,0,{}};
return u;
}
void update(int u,int x){
if(u==0||node[u].d==0) return ;
if(x>>(node[u].d-1)&1){
int s1=node[u].d-1;
swap(node[u].ne[0],node[u].ne[1]);
swap(node[u].has[s1][0],node[u].has[s1][1]);
x&=(1<<(node[u].d-1))-1;
}
node[u].v_xor^=x;
for(int i=0;i<node[u].d;i++)
if(x>>i&1) swap(node[u].has[i][0],node[u].has[i][1]);
}
void push_up(int u){
if(u==0||node[u].d==0) return ;
int l=node[u].ne[0],r=node[u].ne[1],i,s1;
node[u].cnt=node[l].cnt+node[r].cnt;
for(i=node[u].d-2;i>=0;i--){
node[u].has[i][0]=node[l].has[i][0]+node[r].has[i][0];
node[u].has[i][1]=node[l].has[i][1]+node[r].has[i][1];
}
s1=node[u].d-1;
node[u].has[s1][0]=node[l].cnt;
node[u].has[s1][1]=node[r].cnt;
}
void push_down(int u){
if(u==0||node[u].d==0) return ;
if(node[u].v_xor==0) return ;
update(node[u].ne[0],node[u].v_xor);
update(node[u].ne[1],node[u].v_xor);
node[u].v_xor=0;
}
void insert(int x){
// Insert elements only after updating v_xor.
int u=1,i;
stack<int> ned;
for(i=M-1;i>=0;i--){
push_down(u),ned.push(u);
if(node[u].ne[x>>i&1]==0)
node[u].ne[x>>i&1]=make_node(i);
u=node[u].ne[x>>i&1];
}
node[u].cnt++;
while(!ned.empty())
push_up(ned.top()),ned.pop();
}
long long query(int k){
int u=1,i,j,l,r;
long long ans=0;
for(i=M-1;i>=0;i--){
push_down(u);
l=node[u].ne[0];
r=node[u].ne[1];
if(k<=node[l].cnt){
if(v_xor>>i&1) ans+=(1ll<<node[u].d-1)*k;
u=l; continue;
}
if(v_xor>>i&1) ans+=(1ll<<node[u].d-1)*node[l].cnt;
else ans+=(1ll<<node[u].d-1)*(k-node[l].cnt);
for(j=node[l].d-1;j>=0;j--)
ans+=(1ll<<j)*node[l].has[j][!(v_xor>>j&1)];
k-=node[l].cnt,u=r;
}
return ans;
}
void modify_xor(int x){
v_xor^=x;
}
void update_xor(){
update(1,v_xor);
v_xor=0;
}
}trie;
struct Array{
int n,a[N],cnt[N][M][2],v_xor;
void clear(){
n=0,v_xor=0;
}
void insert(int x){
x^=v_xor,a[++n]=x;
for(int i=0;i<M;i++){
cnt[n][i][0]=cnt[n-1][i][0];
cnt[n][i][1]=cnt[n-1][i][1];
cnt[n][i][x>>i&1]++;
}
}
long long query(int k){
long long ans=0;
for(int i=0;i<M;i++)
ans+=(1ll<<i)*cnt[k][i][!(v_xor>>i&1)];
return ans;
}
void modify_xor(int x){
v_xor^=x;
}
void transfer_into_trie(){
for(int i=1;i<=n;i++)
trie.insert(a[i]^v_xor);
}
}arr;
int n,m=0;
int main(){
// freopen("trick.in","r",stdin);
// freopen("trick.out","w",stdout);
int i,q,opt,l,r,x;
long long ans=0;
trie.init_Trie();
scanf("%d",&n);
for(i=1;i<=n;i++){
scanf("%d",&x);
arr.insert(x);
}
scanf("%d",&q);
for(i=1;i<=q;i++){
scanf("%d",&opt);
switch(opt){
case 1:
scanf("%d",&x);
arr.insert(x);
break;
case 2:
scanf("%d%d",&l,&r); l--,ans=0;
if(r<=m) ans+=trie.query(r);
else ans+=trie.query(m)+arr.query(r-m);
if(l<=m) ans-=trie.query(l);
else ans-=trie.query(m)+arr.query(l-m);
printf("%lld\n",ans);
break;
case 3:
scanf("%d",&x);
arr.modify_xor(x);
trie.modify_xor(x);
break;
case 4:
m+=arr.n;
trie.update_xor();
arr.transfer_into_trie();
arr.clear();
}
}
// fclose(stdin);
// fclose(stdout);
return 0;
}
12. CF888G Xor-MST
点击查看题面
给定 \(n\) 个结点的无向完全图，结点 \(i\) 有点权 \(a_i\)。定义边 \((a_i, a_j)\) 的边权为 \(a_i \oplus a_j\)。
求这个图 MST（最小生成树）的权值。
\(1 \leq n \leq 2 \times 10^5\)，\(0 \leq a_i < 2^{30}\)。
点击查看题解
由于这道题的边具有特殊性质，考虑使用 Boruvka 算法。
我们回顾一下 Boruvka 算法的流程。Boruvka 算法共进行 \(\Theta(\log n)\) 轮，每轮如下：
- 找出每个连通块的最小出边。
- 对找出的每条边，合并这条边连接的两个连通块。
考虑使用 Trie 加速寻找出边的过程。
在每轮开始时，维护一个全局的 Trie 记录所有 \(a_i\)；对每个连通块，分别维护一个小的 Trie 记录块内的所有 \(a_i\)。
在每个结点上维护 \(\mathrm{cnt}\)，表示这棵子树内维护了多少个数。
可以考虑对每个点都找到它所在连通块外的最小异或值，连通块的答案即为其中每个结点找出的异或值的最小值。
找到最小异或值，可以先在 Trie 上找到这个 \(a_i\) 对应的链，再从下往上判断每个结点的另一个儿子是否有指向块外的边。
对于一个点，要判断是否有指向块外的边，只需判断全局 Trie 和该连通块的 Trie 的对应节点的 \(\mathrm{cnt}\) 是否相同即可。
合并连通块时需要同时合并 Trie。
时间复杂度为 \(\Theta(n \cdot \log n \cdot \log V)\)，其中 \(V\) 为值域。
点击查看代码
#include <algorithm>
#include <cstdio>
#include <iostream>
using namespace std;
const int N=200003,M=30;
const int PIN=2147483647;
struct Trie{
struct Node{
int ne[2],cnt,num;
}node[N*M*2];
int len_node=0;
int make_node(){
int u=++len_node;
node[u]={{0,0},0,0};
return u;
}
int merge(int u,int v){
if(u==0||v==0) return max(u,v);
node[u].cnt+=node[v].cnt;
node[u].ne[0]=merge(node[u].ne[0],node[v].ne[0]);
node[u].ne[1]=merge(node[u].ne[1],node[v].ne[1]);
return u;
}
void insert(int u,int x,int y){
for(int i=M-1;i>=0;i--){
node[u].cnt++;
if(node[u].ne[x>>i&1]==0)
node[u].ne[x>>i&1]=make_node();
u=node[u].ne[x>>i&1];
}
node[u].cnt++,node[u].num=y;
}
int query(int p,int q,int x){
int sp=p,sq=q,i,s1=M,s2,s3;
for(i=M-1;i>=0;i--){
s2=node[p].ne[!(x>>i&1)];
s3=node[q].ne[!(x>>i&1)];
if(node[s2].cnt!=node[s3].cnt)
s1=i,sp=s2,sq=s3;
p=node[p].ne[x>>i&1];
q=node[q].ne[x>>i&1];
}
if(node[q].cnt-node[p].cnt>0)
return node[q].num;
p=sp,q=sq;
if(s1==M) return -1;
for(i=s1-1;i>=0;i--){
s2=node[p].ne[x>>i&1];
s3=node[q].ne[x>>i&1];
if(node[s2].cnt!=node[s3].cnt)
p=s2,q=s3;
else{
p=node[p].ne[!(x>>i&1)];
q=node[q].ne[!(x>>i&1)];
}
}
return node[q].num;
}
}trie;
int n,a[N],ft[N],root[N],alrt;
int bx[N],bu[N];
int find(int u){
if(ft[u]==u) return u;
return ft[u]=find(ft[u]);
}
long long Boruvka(){
int i,cnt=0,s1;
long long ans=0;
alrt=trie.make_node();
for(i=1;i<=n;i++)
trie.insert(alrt,a[i],i);
for(i=1;i<=n;i++){
ft[i]=i,root[i]=trie.make_node();
trie.insert(root[i],a[i],i);
}
while(cnt<n-1){
for(i=1;i<=n;i++)
bx[i]=PIN,bu[i]=-1;
for(i=1;i<=n;i++){
s1=trie.query(root[find(i)],alrt,a[i]);
if(s1==-1) continue;
if((a[s1]^a[i])<bx[find(i)])
bx[find(i)]=a[s1]^a[i],bu[find(i)]=s1;
}
for(i=1;i<=n;i++){
if(find(i)!=i||bu[i]==-1) continue;
if(find(i)==find(bu[i])) continue;
ans+=bx[i],ft[i]=ft[bu[i]],cnt++;
root[ft[bu[i]]]=trie.merge(root[i],root[ft[bu[i]]]);
}
}
return ans;
}
int main(){
// freopen("Xor-MST.in","r",stdin);
// freopen("Xor-MST.out","w",stdout);
int i;
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
sort(a+1,a+n+1);
printf("%lld",Boruvka());
// fclose(stdin);
// fclose(stdout);
return 0;
}
13. CF840E In a Trap
点击查看题面
给定一棵 \(n\) 个点的树，以 \(1\) 为根，点 \(i\) 有点权 \(a_i\)。
\(q\) 次询问，每次询问路径 \(u\) 到 \(v\) 上最大的 \(a_i \oplus \operatorname{dist}(i, v)\)，保证 \(u\) 为 \(v\) 的祖先。
\(1 \leq n \leq 5 \times 10^4\)，\(1 \leq q \leq 1.5 \times 10^5\)，\(0 \leq a_i \leq n\)。
点击查看题解
由于保证了 \(u\) 是 \(v\) 的祖先，我们实际上要最大化 \(a_i \oplus (\operatorname{dep}(v) - \operatorname{dep}(i))\) 的值。
暴力跳父亲是 \(\Theta(nq)\) 的，无法接受。考虑优化这个暴力。
我们考虑分块。我们希望一次能够向上跳 \(B\) 个点，这样我们就能在 \(\Theta(nB)\) 预处理、\(\Theta(\dfrac{nq}{B} + qB)\) 查询的时间复杂度内解决问题。
但由于这是异或，且表达式内与块外点有关的项 \(\operatorname{dep}(i)\) 无法分离出来，普通的 \(B\) 很难支持预处理操作。
为了减小预处理的难度，我们取特殊值 \(B = 2^m\)。这样在每次跳 \(B\) 个点的过程中，表达式 \(\operatorname{dep}(v) - \operatorname{dep}(i)\) 后 \(m\) 位的值就与块外点 \(i\) 无关了。
我们只需考虑前 \(\log \dfrac{n}{B} = 16 - m\) 位的值，这些值难以通过预处理直接求得。
但我们发现 \(\Theta(\dfrac{n}{B})\) 已经比 \(\Theta(n)\) 少了好几个数量级。因此，我们不妨对前 \(16 - m\) 位每种可能的值 \(i\)，都预处理出 \(f(u, i)\) 表示从 \(u\) 开始向上 \(B\) 个数中，若 \(\operatorname{dep}(v) - \operatorname{dep}(i)\) 的前 \(16 - m\) 位均为 \(i\)，则题目中表达式的最大值。
询问时，在跳的过程中容易维护 \(\operatorname{dep}(v) - \operatorname{dep}(i)\) 前 \(16 - m\) 位的值，直接查询即可。
问题转化为如何快速地预处理出 \(f(u, i)\) 的值。我们发现这等价于最大异或和问题。把 \(u\) 的 \(B\) 级祖先以下的点权全部丢进 Trie 中，对每个 \(i \times B\) 跑最大异或和即可。
时间复杂度为 \(\Theta(nB \cdot \log n + \dfrac{nq}{B} + qB)\)。取 \(m = 8, B = 256\) 即可。
点击查看代码
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int N=50003,M=8;
struct Trie{
int len_node=0,node[(1<<M)*M][2];
void clear(){
len_node=1;
node[1][0]=node[1][1]=0;
}
int make_node(){
int u=++len_node;
node[u][0]=node[u][1]=0;
return u;
}
void insert(int x){
int cur=1,i;
for(i=M-1;i>=0;i--){
if(node[cur][x>>i&1]==0)
node[cur][x>>i&1]=make_node();
cur=node[cur][x>>i&1];
}
}
int query(int x){
int cur=1,i,ans=x;
for(i=M-1;i>=0;i--)
if(node[cur][!(x>>i&1)]>0)
cur=node[cur][!(x>>i&1)],ans^=1<<i;
else cur=node[cur][x>>i&1];
return ans;
}
}trie;
int n,a[N],fa[N],dep[N],to[N];
int f[N][1<<M],g[N][1<<M];
int len_list=0,e[N*2],ne[N*2],h[N];
void add_once(int a,int b){
e[len_list]=b;
ne[len_list]=h[a];
h[a]=len_list++;
}
void add_twice(int a,int b){
add_once(a,b);
add_once(b,a);
}
void dfs(int u,int father,int depth){
fa[u]=father,dep[u]=depth,trie.clear();
for(int i=0,j=u;i<(1<<M)&&j>0;i++,j=to[u]=fa[j]){
f[u][a[j]>>M]=max(f[u][a[j]>>M],a[j]^i);
trie.insert(a[j]>>M);
}
for(int i=0;i<(1<<M);i++)
g[u][i]=trie.query(i);
for(int i=h[u];i>=0;i=ne[i])
if(e[i]!=fa[u]) dfs(e[i],u,depth+1);
}
int main(){
// freopen("trap.in","r",stdin);
// freopen("trap.out","w",stdout);
int i,j,k,q,x,y,s1,ans;
scanf("%d%d",&n,&q);
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
memset(h,-1,sizeof h);
for(i=1;i<n;i++){
scanf("%d%d",&x,&y);
add_twice(x,y);
}
dfs(1,0,1);
for(i=1;i<=q;i++){
scanf("%d%d",&x,&y),ans=0;
for(j=y,k=0;dep[to[j]]>=dep[x];j=to[j],k++)
ans=max(ans,f[j][g[j][k]]^(k<<M));
while(j!=x) ans=max(ans,a[j]^(dep[y]-dep[j])),j=fa[j];
ans=max(ans,a[x]^(dep[y]-dep[x]));
printf("%d\n",ans);
}
// fclose(stdin);
// fclose(stdout);
return 0;
}
14. CF-gym-102331-B Bitwise Xor
点击查看题面
给定一个长为 \(n\) 的序列 \(a\)，和一个整数 \(x\)。
定义一个合法的非空序列为：任取序列中两个正整数 \(p, q\)，都有 \(p \oplus q \geq x\)。
求 \(a\) 中合法非空子序列的个数，答案对 \(998244353\) 取模。
\(1 \leq n \leq 3 \times 10^5\)，\(0 \leq a_i, x < 2^{60}\)。
点击查看题解
假设我们已经找到了一个序列 \(b\)，考虑如何判断它是否合法。
我们希望让相邻的数异或值尽可能小，因此考虑将 \(b\) 排序。那么我们很容易得出 \(b\) 合法的一个必要条件：
\(b\) 中任意两个相邻的数 \(p, q\) 都满足 \(p \oplus q \geq x\)。
感性理解一下，我们对 \(b\) 排序会使得相邻的数异或值变小。因此，我们猜测这也是充分条件。
我们发现，\(x\) 一定是这么构成的：前面一串前导 \(0\)，跟一个 \(1\)，后面再跟一个 0-1 串。
考虑序列中任意两个数 \(s, t(s < t)\)。如果在 \(x\) 前导 \(0\) 对应的位中存在某一位，\(s\) 和 \(t\) 在这位上的数字不相同，那么 \(s \oplus t\) 的值在这一位上一定是 \(1\)，也就是说此时必有 \(s \oplus t \geq x\)。
因此我们不妨设 \(s\) 和 \(t\) 在 \(x\) 前导 \(0\) 的位上的值都相同。
我们将序列中 \(s\) 到 \(t\) 的子段取出来，令其位序列 \(c\)，即 \(s = c_1 \leq c_2 \leq \cdots \leq c_k = t\)。
显然 \(c\) 中的数在这些位上的值都相同。而由于 \(c_i \oplus c_{i + 1} \geq x\)，对于 \(x\) 的最高位，任意两个相邻的 \(c_i\) 在这一位上的值一定不同。
而由于这个序列有序，任意两个相邻的 \(c_i\) 在这一位上的值一定单调不降。因此，这个序列的长度只可能为 \(k = 2\)。
也就是说 \(s\) 和 \(t\) 一定相邻。因此，这个条件也是充分条件。
于是，我们找到了一个能在 \(\Theta(n)\) 复杂度内判断序列是否合法的算法。
考虑原问题怎么做。我们不妨也将 \(a_i\) 排序。
由上述分析，我们只需考虑子序列中任意两个相邻的 \(a_i\) 是否满足条件。因此考虑 DP。
设 \(f_i\) 表示以 \(i\) 结尾的合法非空子序列的个数。显然有如下转移：
- 若子序列长度为 \(1\)，则有 \(f_i \leftarrow 1\)。
- 若子序列长度大于 \(1\)，枚举 \(i\) 的上一个位置 \(j\)，则有 \(f_i \leftarrow f_j[a_i \oplus a_j \geq x]\)。
第二种转移可以用 Trie 进行优化。
时间复杂度为 \(\Theta(n \cdot \log V)\)，其中 \(V\) 为值域。
点击查看代码
#include <algorithm>
#include <cstdio>
using namespace std;
const int N=300003,M=60,mod=998244353;
struct Trie{
struct Node{
int ne[2],cnt,f;
}node[N*M];
int len_node;
long long k;
void init_Trie(long long _k){
len_node=1,k=_k;
}
void modify(long long x,int y){
int cur=1,i;
node[cur].f=(node[cur].f+y)%mod;
for(i=M-1;i>=0;i--){
if(node[cur].ne[x>>i&1]==0)
node[cur].ne[x>>i&1]=++len_node;
cur=node[cur].ne[x>>i&1];
node[cur].f=(node[cur].f+y)%mod;
}
}
int query(long long x){
int cur=1,i,ans=0;
for(i=M-1;i>=0;i--)
if(!(k>>i&1)){
ans=(ans+node[node[cur].ne[!(x>>i&1)]].f)%mod;
cur=node[cur].ne[x>>i&1];
}
else cur=node[cur].ne[!(x>>i&1)];
ans=(ans+node[cur].f)%mod;
return ans;
}
}trie;
int n,f[N];
long long a[N];
int main(){
// freopen("xor.in","r",stdin);
// freopen("xor.out","w",stdout);
int i,ans=0;
long long k;
scanf("%d%lld",&n,&k);
for(i=1;i<=n;i++)
scanf("%lld",&a[i]);
sort(a+1,a+n+1);
trie.init_Trie(k);
for(i=1;i<=n;i++){
f[i]=(trie.query(a[i])+1)%mod;
trie.modify(a[i],f[i]);
ans=(ans+f[i])%mod;
}
printf("%d",ans);
// fclose(stdin);
// fclose(stdout);
return 0;
}
15. CF1616H Keep XOR Low
点击查看题面
给定一个长为 \(n\) 的序列 \(a\)，和一个整数 \(x\)。
定义一个合法的非空序列为：任取序列中两个正整数 \(p, q\)，都有 \(p \oplus q \leq x\)。
求 \(a\) 中合法非空子序列的个数，答案对 \(998244353\) 取模。
\(1 \leq n \leq 1.5 \times 10^5\)，\(0 \leq a_i, x < 2^{30}\)。
点击查看题解
题面和上一题非常相似，只不过把“大于等于”改成了“小于等于”。但做法截然不同。
我们发现，\(x\) 一定是这么构成的：前面一串前导 \(0\)，跟一个 \(1\)，后面再跟一个 0-1 串。
显然在 \(x\) 的前导 \(0\) 对应的数位上，一个合法序列中的数应相同。我们现在考虑 \(x\) 的最高位。
如果序列中的数在这一位上仍然全部相同，那么显然这个序列一定合法，统计答案即可。
因此只需考虑序列中的数在这一位上既有 \(0\) 又有 \(1\) 的情况。
我们可以将该序列划分成两个非空子集：\(P\) 包含序列中这一位为 \(0\) 的数，\(Q\) 包含序列中这一位为 \(1\) 的数。
容易发现，\(P\) 和 \(Q\) 各自的内部一定满足条件。因此只需考虑 \(P\) 和 \(Q\) 之间的数是否满足条件。
感性理解一下，我们发现这个问题是可以递归处理的。
我们令 \(\operatorname{query}(d, p, q)\) 表示：若集合 \(p\)、\(q\) 各自内部的数只有后 \(d + 1\) 位不同且 \(p \cap q = \emptyset\)，要在 \(p \cup q\) 内选数使得选出的数在 \(p\)、\(q\) 内都有且选出的数能构成合法非空序列，求这样选数的方案数。
（我们默认 \(p\)、\(q\) 各自内部选出的数都是满足条件的，只需考虑 \(p\)、\(q\) 之间选出的数是否满足条件。）
我们发现要求 \(p\)、\(q\) 前缀相同的条件能用 Trie 轻松处理，因此我们把集合 \(p\)、\(q\) 都对应到 Trie 上的结点。
我们用 \(p_0\) 表示 \(p\) 的 \(0\) 儿子，\(p_1\) 表示 \(p\) 的 \(1\) 儿子，\(q_0\) 表示 \(q\) 的 \(0\) 儿子，\(q_1\) 表示 \(q\) 的 \(1\) 儿子。
想清楚了 \(\operatorname{query}\) 的定义，递归的过程就很简单了。显然有
- 若 \(x\) 的第 \(d\) 位为 \(0\)，则只需把 \(\operatorname{query}(d - 1, p_0, q_0)\) 和 \(\operatorname{query}(d - 1, p_1, q_1)\) 相加即可。
- 若 \(x\) 的第 \(d\) 位为 \(1\)，则先求出 \(\operatorname{query}(d - 1, p_0, q_1)\) 和 \(\operatorname{query}(d - 1, p_1, q_0)\) 的值，然后把各种情况分类讨论一下即可。
具体细节见代码。
显然 Trie 上每个结点只会遍历一次，时间复杂度为 \(\Theta(n \cdot \log V)\)。
点击查看代码
#include <cstdio>
const int N=150003,M=30,mod=998244353;
int n,x,a[N],pow2[N+3];
struct Trie{
struct Node{
int ne[2],cnt;
}node[N*(M+1)];
int len_node;
void init_Trie(){
len_node=1;
node[1]={{0,0},0};
}
void insert(int x){
int cur=1,i;
node[cur].cnt++;
for(i=M-1;i>=0;i--){
if(node[cur].ne[x>>i&1]==0)
node[cur].ne[x>>i&1]=++len_node;
cur=node[cur].ne[x>>i&1];
node[cur].cnt++;
}
}
int query(int d,int p,int q){ // 即上文提到的 query 函数
if(p==0||q==0) return 0;
if(d==-1){
int ans=1;
ans=(long long)ans*(pow2[node[p].cnt]-1)%mod;
ans=(long long)ans*(pow2[node[q].cnt]-1)%mod;
return ans;
}
int ans=0;
if(!(x>>d&1)){
ans=(ans+query(d-1,node[p].ne[0],node[q].ne[0]))%mod;
ans=(ans+query(d-1,node[p].ne[1],node[q].ne[1]))%mod;
return ans;
}
int p0=node[p].ne[0],p1=node[p].ne[1];
int q0=node[q].ne[0],q1=node[q].ne[1];
int s1=query(d-1,p0,q1),s2=query(d-1,p1,q0);
ans=(ans+(long long)(pow2[node[p0].cnt]-1)*(pow2[node[q0].cnt]-1)%mod)%mod; // 只选 p0 和 q0 中的数
ans=(ans+(long long)(pow2[node[p1].cnt]-1)*(pow2[node[q1].cnt]-1)%mod)%mod; // 只选 p1 和 q1 中的数
ans=(ans+((long long)pow2[node[p1].cnt]+pow2[node[q0].cnt]-1)*s1%mod)%mod; // 必选 p0 和 q1 中的数，可选 p1、q0 中的数（但不能都选）
ans=(ans+((long long)pow2[node[p0].cnt]+pow2[node[q1].cnt]-1)*s2%mod)%mod; // 必选 p1 和 q0 中的数，可选 p0、q1 中的数（但不能都选）
ans=(ans+(long long)s1*s2%mod)%mod; // p0、p1、q0、q1 每个集合中都必须有数被选
return ans;
}
int solve(int u,int d){ // 在 x 的前导 0 对应的数位中，在 trie 上 dfs
if(u==0) return 0;
if(d==-1) return pow2[node[u].cnt]-1;
int ans=0;
if(!(x>>d&1)){
ans=(ans+solve(node[u].ne[0],d-1))%mod;
ans=(ans+solve(node[u].ne[1],d-1))%mod;
return ans;
}
ans=(ans+pow2[node[node[u].ne[0]].cnt]-1)%mod;
ans=(ans+pow2[node[node[u].ne[1]].cnt]-1)%mod;
ans=(ans+query(d-1,node[u].ne[0],node[u].ne[1]))%mod;
return ans;
}
}trie;
int main(){
// freopen("low.in","r",stdin);
// freopen("low.out","w",stdout);
int i;
scanf("%d%d",&n,&x);
for(i=1,pow2[0]=1;i<=n;i++)
pow2[i]=pow2[i-1]*2%mod;
trie.init_Trie();
for(i=1;i<=n;i++){
scanf("%d",&a[i]);
trie.insert(a[i]);
}
printf("%d",trie.solve(1,M-1));
// fclose(stdin);
// fclose(stdout);
return 0;
}
16. 洛谷 P10218 [省选联考 2024] 魔法手杖
点击查看题面
给定 \(a_1, a_2, \cdots, a_n\) 以及 \(b_1, b_2, \cdots, b_n\)，满足 \(a_i \in [0, 2^k)\) 以及 \(b_i \geq 0\)，你需要给出 \(S \subseteq \{1, 2, \cdots, n\}\) 以及 \(x \in [0, 2^k)\) 满足以下条件：
- \(\sum_{i \in S} b_i \leq m\)；
- 满足以上条件的前提下，最大化 \(\operatorname{val}(S, x) = \min\{\min_{i \in S}\{a_i + x\}, \min_{i \in U \setminus S}\{a_i \oplus x\}\}\) 的值。
你只需要给出最大的 \(\operatorname{val}(S, x)\) 的值即可。
多组测试数据。
\(1 \leq n \leq 10^5\)，\(1 \leq \sum n \leq 5 \times 10^5\)，\(0 \leq b_i, m \leq 10^9\)，\(0 \leq k \leq 120\)。
如何做到 $\Theta(nk^2)$？
看到 \(\min\) 的嵌套，想到二分。令二分出的数为 \(\mathrm{ans}\)，需要判断操作后每个 \(a_i\) 是否都能大于等于 \(\mathrm{ans}\)。
由于运算是异或和加，我们发现这个东西可以从高到低逐位判断。因此考虑在 Trie 树上 dfs。
与上一题相同，我们令 Trie 树上的结点与前缀相同的二进制数集合一一对应。
对于每个 \(a_i\)，由于异或是不进位加法，因此 \(a_i \oplus x \leq a_i + x\)。
因此仅当所有 \(a_i\) 都满足 \(a_i + x \geq \mathrm{ans}\) 时，\(\operatorname{val}\) 才可能合法。由此，我们计算出 \(x\) 的最小值 \(y = \mathrm{ans} - \min_{i = 1}^n a_i\)。
容易发现此时只要 \(a_i\) 被选入集合 \(S\)，关于 \(a_i\) 的决策就一定符合条件。
令 \(\operatorname{check}(u, d, m, y, \mathrm{ans})\) 表示只考虑 \(u\) 中的数和所有数的后 \(d + 1\) 位，是否存在一个划分使得 \(b\) 之和小于等于 \(m\)、待决策的 \(x\) 值大于等于 \(y\)、答案大于等于 \(\mathrm{ans}\)。
我们令 \(l\) 表示 \(u\) 的 \(0\) 儿子，我们令 \(r\) 表示 \(u\) 的 \(1\) 儿子。
考虑如何求出 \(\operatorname{check}\) 的答案。我们按 \(y\) 和 \(\mathrm{ans}\) 在第 \(d\) 位的值分类讨论：
（\(s_u\) 表示集合 \(u\) 中数的 \(b\) 值之和）
- 若 \(\mathrm{ans}\) 为 \(0\)、\(y\) 为 \(0\)：
- 若 \(x\) 的这一位填 \(0\)，则异或后 \(r\) 的这一位一定为 \(1\)，因此答案为 \(\operatorname{check}(l, d - 1, m, y, \mathrm{ans})\)。
- 若 \(x\) 的这一位填 \(1\)，则异或后 \(l\) 的这一位一定为 \(1\)，因此答案为 \(\operatorname{check}(r, d - 1, m, 0, \mathrm{ans})\)。
- 若 \(\mathrm{ans}\) 为 \(0\)、\(y\) 为 \(1\)：
- \(x\) 的这一位必填 \(1\)，异或后 \(l\) 的这一位一定为 \(1\)，因此答案为 \(\operatorname{check}(r, d - 1, m, y, \mathrm{ans})\)。
- 若 \(\mathrm{ans}\) 为 \(1\)、\(y\) 为 \(0\)：
- 若 \(x\) 的这一位填 \(0\)，那么 \(l\) 一定要选入 \(S\) 进行加法，因此答案为 \(\operatorname{check}(r, d - 1, m - s_l, y, \mathrm{ans})\)。
- 若 \(x\) 的这一位填 \(1\)，那么 \(r\) 一定要选入 \(S\) 进行加法，因此答案为 \(\operatorname{check}(l, d - 1, m - s_r, 0, \mathrm{ans})\)。
- 若 \(\mathrm{ans}\) 为 \(1\)、\(y\) 为 \(1\)：
- \(x\) 的这一位必填 \(1\)，\(r\) 一定要选入 \(S\) 进行加法，因此答案为 \(\operatorname{check}(l, d - 1, m - s_r, y, \mathrm{ans})\)。
容易发现每次判断都只会遍历 Tre 上的每个结点 \(1\) 次。因此每次判断的时间复杂度为 \(\Theta(nk)\)。
总时间复杂度为 \(\Theta(nk^2)\)，能获得 \(72\) 分。
如何做到 $\Theta(nk)$？
我们考虑二分的实质，实际上是从高到低依次决策 \(\mathrm{ans}\) 的每一位是否填 \(1\)。
我们感性地理解，每一次决策都要从头重新 \(\operatorname{check}\) 一遍，非常浪费时间。
而在 \(\operatorname{check}\) 的过程中，由于返回 \(0\) 的条件只有 \(m < 0\)，因此可以忽略还未轮到进行决策的数位。
由上面感性的分析，我们发现 \(ans\) 的第 \(p\) 位可以只在递归的第 \(k - p\) 层被决策。
我们考虑去掉二分，在递归的过程中决策 \(\mathrm{ans}\) 的每一位。
我们令 \(\operatorname{query}(u, d, \mathrm{minn}, m, y, \mathrm{ans})\) 表示只考虑集合 \(u\) 中的数的后 \(d + 1\) 位，答案的前 \(k - d - 1\) 位为 \(\mathrm{ans}\)，\(x\) 的前 \(k - d - 1\) 位为 \(y\)，已经选进 \(S\) 要执行加法操作的数的最小值为 \(\mathrm{minn}\)，若要使剩余的 \(S\) 中的数的 \(b\) 之和小于等于 \(m\)，求 \(ans\) 的最小值。
每次递归我们先要决策 \(\mathrm{ans}\) 的第 \(d\) 位是否为 \(1\)。
我们记 \(t_u\) 表示集合 \(u\) 中的数的最小值。
假设 \(\mathrm{ans}\) 的第 \(d\) 位为 \(1\)。那么 \(\mathrm{ans}\) 需满足以下两个情况之一。
- 若 \(x\) 的第 \(i\) 位填 \(0\)，那么 \(l\) 中的数一定被选入 \(S\) 进行加操作，因此首先需要满足 \(s_l \leq m\)。然后我们需要判断是否存在一种满足条件的情况，我们贪心地选择一种限制最宽松的情况（即 \(\mathrm{ans}\) 剩余的位置全填 \(0\)，\(x\) 剩余的位置全填 \(1\)）。这种情况下，异或的数一定满足条件，加法的数满足条件当且仅当 \(\min\{\mathrm{minn}, t_l\} + x + 2^d - 1 \geq \mathrm{ans} + 2^d\)。
- 若 \(x\) 的第 \(i\) 位填 \(1\)，同上一种情况的理，满足条件当且仅当 \(s_r \leq m\) 且 \(\min\{\mathrm{minn}, t_r\} + x + 2^d + 2^d - 1 \geq \mathrm{ans} + 2^d\)。
若 \(\mathrm{ans}\) 满足以下两个情况之一的所有条件，则 \(\mathrm{ans}\) 的第 \(d\) 位填 \(1\)。
然后递归决策即可。
容易发现每个结点仍然最多遍历 \(1\) 次。因此时间复杂度为 \(\Theta(nk)\)。
复杂度为 $\Theta(nk^2)$ 的代码
#include <cstdio>
#include <iostream>
#include <stack>
using namespace std;
const int N=(int)1e5+3,M=120;
int n,m,p,b[N];
__int128 a[N],pow2[M+3];
struct Trie{
struct Node{
int ne[2];
long long sum;
}node[N*M];
int len_node;
void clear(){
len_node=1;
node[1]={{0,0},0};
}
int make_node(){
int u=++len_node;
node[u]={{0,0},0};
return u;
}
void insert(__int128 x,int y){
int cur=1,i;
node[cur].sum+=y;
for(i=p-1;i>=0;i--){
if(node[cur].ne[x>>i&1]==0)
node[cur].ne[x>>i&1]=make_node();
cur=node[cur].ne[x>>i&1];
node[cur].sum+=y;
}
}
bool check(int u,int d,long long m,__int128 x,__int128 ans){
if(m<0) return 0;
if(u==0||d<0) return 1;
int l=node[u].ne[0],r=node[u].ne[1];
if(!(ans>>d&1)&&!(x>>d&1)){
if(check(l,d-1,m,x,ans)) return 1;
if(check(r,d-1,m,0,ans)) return 1;
return 0;
}
if(!(ans>>d&1))
return check(r,d-1,m,x,ans);
if(!(x>>d&1)){
if(check(r,d-1,m-node[l].sum,x,ans)) return 1;
if(check(l,d-1,m-node[r].sum,0,ans)) return 1;
return 0;
}
return check(l,d-1,m-node[r].sum,x,ans);
}
}trie;
__int128 read(){
__int128 x=0; char ch;
do
ch=getchar();
while(ch<'0'||ch>'9');
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
return x;
}
void write(__int128 x){
stack<char> stk;
while(x>0)
stk.push(x%10+'0'),x/=10;
if(stk.empty()) stk.push('0');
while(!stk.empty())
putchar(stk.top()),stk.pop();
}
int main(){
// freopen("xor.in","r",stdin);
// freopen("xor.out","w",stdout);
int i,t,s1; __int128 ans,s2,minn;
for(i=1,pow2[0]=1;i<=M;i++)
pow2[i]=pow2[i-1]*2;
for(s1=read(),t=read();t>0;t--){
n=read(),m=read(),p=read();
for(i=1;i<=n;i++) a[i]=read();
for(i=1;i<=n;i++) b[i]=read();
trie.clear(),ans=s2=0,minn=pow2[p];
for(i=1;i<=n;i++) minn=min(minn,a[i]);
for(i=1;i<=n;i++) s2+=b[i];
if(s2<=m){
write(minn+pow2[p]-1),putchar('\n');
continue;
}
for(i=1;i<=n;i++)
trie.insert(a[i],b[i]);
for(i=p-1;i>=0;i--){
s2=max(ans+pow2[i]-minn,(__int128)0);
if(trie.check(1,p-1,m,s2,ans+pow2[i])) ans+=pow2[i];
}
write(ans),putchar('\n');
}
// fclose(stdin);
// fclose(stdout);
return 0;
}
复杂度为 $\Theta(nk)$ 的代码
#include <cstdio>
#include <iostream>
#include <stack>
using namespace std;
const int N=(int)1e5+3,M=120;
int n,m,p,b[N];
__int128 a[N],pow2[M+3];
struct Trie{
struct Node{
int ne[2];
long long sum;
__int128 minn;
}node[N*M];
int len_node;
void clear(){
len_node=1;
node[1]={{0,0},0,pow2[p]};
node[0]={{0,0},0,pow2[p]};
}
int make_node(){
int u=++len_node;
node[u]={{0,0},0,pow2[p]};
return u;
}
void insert(__int128 x,int y){
int cur=1,i;
node[cur].minn=min(node[cur].minn,x);
node[cur].sum+=y;
for(i=p-1;i>=0;i--){
if(node[cur].ne[x>>i&1]==0)
node[cur].ne[x>>i&1]=make_node();
cur=node[cur].ne[x>>i&1];
node[cur].minn=min(node[cur].minn,x);
node[cur].sum+=y;
}
}
void query(int u,int d,__int128 minn,long long m,__int128 x,__int128& ans){
if(u==0||d<0){ ans=min(minn+x,ans)+pow2[d+1]-1; return ; }
__int128 s1=ans,s2=ans; bool bj=0;
int l=node[u].ne[0],r=node[u].ne[1];
s1+=pow2[d],s2+=pow2[d];
if(node[r].sum<=m&&min(minn,node[r].minn)+x+pow2[d+1]-1>=s1)
query(l,d-1,min(minn,node[r].minn),m-node[r].sum,x|pow2[d],s1),bj=1;
if(node[l].sum<=m&&min(minn,node[l].minn)+x+pow2[d]-1>=s2)
query(r,d-1,min(minn,node[l].minn),m-node[l].sum,x,s2),bj=1;
if(bj){ ans=max(s1,s2); return ; }
query(l,d-1,minn,m,x,s1=ans);
query(r,d-1,minn,m,x|pow2[d],s2=ans);
ans=max(s1,s2);
}
}trie;
__int128 read(){
__int128 x=0; char ch;
do
ch=getchar();
while(ch<'0'||ch>'9');
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
return x;
}
void write(__int128 x){
stack<char> stk;
while(x>0)
stk.push(x%10+'0'),x/=10;
if(stk.empty()) stk.push('0');
while(!stk.empty())
putchar(stk.top()),stk.pop();
}
int main(){
// freopen("xor.in","r",stdin);
// freopen("xor.out","w",stdout);
int i,t,s1; __int128 ans,s2,minn;
for(i=1,pow2[0]=1;i<=M;i++)
pow2[i]=pow2[i-1]*2;
for(s1=read(),t=read();t>0;t--){
n=read(),m=read(),p=read();
for(i=1;i<=n;i++) a[i]=read();
for(i=1;i<=n;i++) b[i]=read();
trie.clear(),ans=s2=0,minn=pow2[p];
for(i=1;i<=n;i++) minn=min(minn,a[i]);
for(i=1;i<=n;i++) s2+=b[i];
if(s2<=m){
write(minn+pow2[p]-1),putchar('\n');
continue;
}
for(i=1;i<=n;i++)
trie.insert(a[i],b[i]);
trie.query(1,p-1,pow2[p],m,0,ans=0);
write(ans),putchar('\n');
}
// fclose(stdin);
// fclose(stdout);
return 0;
}