智商有点下线想复杂了.
我的做法是考虑树剖，这样每个查询可以看做序列上至多$\mathcal O(\log n)$段的查询.最大异或值可以用trie来做，那么就可以把询问离线然后在线段树上对trie做启发式合并了. 其实可以不用写启发式合并，写一个类似线段树合并的东西. 这样做是三个$\log$的，但是树剖的那个$\log$很小，所以可以过.
但是其实只需要用可持久化trie做就可以了……
代码：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
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
using namespace std;
struct edge{
ele v;
edge *nxt;
}ep[maxn<<1],*ecnt;
struct tn{
tn *c[2];
}tnp[maxn*(maxk+2)],*tncnt;
struct node{
tn *t;
vector<ele> v;
node *l,*r;
}np[maxn<<2],*ncnt;
ele n,Q,tcnt,v[maxn],seq[maxn],dfn[maxn],fa[maxn],size[maxn],dep[maxn],r[maxn],a[maxn],res[maxn];
edge *h[maxn],*hc[maxn];
node *root;
inline void addedge(ele u,ele v){
edge *p=ecnt++;
p->v=v; p->nxt=h[u];
h[u]=p;
}
inline ele getv(ele x,ele i){
return (x>>i)&1;
}
tn* ins(tn *x,ele y,ele i){
if (!x){
x=tncnt++;
x->c[0]=x->c[1]=NULL;
}
if (~i) x->c[getv(y,i)]=ins(x->c[getv(y,i)],y,i-1);
return x;
}
tn* merge(tn *x,tn *y){
if (!x) return y;
if (!y) return x;
x->c[0]=merge(x->c[0],y->c[0]);
x->c[1]=merge(x->c[1],y->c[1]);
return x;
}
node* build(ele l,ele r){
node *p=ncnt++;
p->v.clear();
if (l==r) p->t=ins(NULL,v[seq[l]],maxk),p->l=p->r=NULL;
else{
ele mid=(l+r)>>1;
p->l=build(l,mid);
p->r=build(mid+1,r);
}
return p;
}
void upd(node *x,ele a,ele b,ele l,ele r,ele i){
if (l<=a && b<=r) x->v.push_back(i);
else{
ele mid=(a+b)>>1;
if (l<=mid) upd(x->l,a,mid,l,r,i);
if (mid<r) upd(x->r,mid+1,b,l,r,i);
}
}
void dfs1(ele p,ele i){
size[i]=1;
hc[i]=NULL;
fa[i]=p;
for (edge *j=h[i]; j; j=j->nxt)
if (j->v!=p){
dep[j->v]=dep[i]+1;
dfs1(i,j->v);
size[i]+=size[j->v];
if (!hc[i] || size[j->v]>size[hc[i]->v]) hc[i]=j;
}
}
void dfs2(ele p,ele i){
dfn[i]=tcnt; seq[tcnt++]=i;
if (hc[i]){
r[hc[i]->v]=r[i];
dfs2(i,hc[i]->v);
}
for (edge *j=h[i]; j; j=j->nxt)
if (j->v!=p && j!=hc[i]){
r[j->v]=j->v;
dfs2(i,j->v);
}
}
inline ele lca(ele x,ele y){
while (r[x]!=r[y]){
if (dep[r[x]]<dep[r[y]]) swap(x,y);
x=fa[r[x]];
}
return dep[x]<dep[y]?x:y;
}
inline void upd(ele x,ele y,ele i){
while (~x && dep[x]>dep[y]){
if (dep[r[x]]>dep[y]) upd(root,0,n-1,dfn[r[x]],dfn[x],i);
else upd(root,0,n-1,dfn[y]+1,dfn[x],i);
x=fa[r[x]];
}
}
ele qry(tn *x,ele y,ele i){
if (!~i) return 0;
ele t=getv(y,i)^1;
ele ans=x->c[t]?qry(x->c[t],y,i-1)+(1<<i):qry(x->c[t^1],y,i-1);
return ans;
}
void dfs3(node *x){
if (x->l){
dfs3(x->l);
dfs3(x->r);
x->t=merge(x->l->t,x->r->t);
}
for (int j=0; j<x->v.size(); ++j){
ele i=x->v[j];
res[i]=max(res[i],qry(x->t,a[i],maxk));
}
}
int main(){
scanf("%d%d",&n,&Q);
for (int i=0; i<n; ++i) scanf("%d",v+i);
ecnt=ep; memset(h,0,sizeof(h));
for (int i=0; i<n-1; ++i){
ele u,v;
scanf("%d%d",&u,&v); --u,--v;
addedge(u,v); addedge(v,u);
}
dep[0]=0;
dfs1(-1,0);
tcnt=0; r[0]=0;
dfs2(-1,0);
ncnt=np; tncnt=tnp;
root=build(0,n-1);
for (int i=0; i<Q; ++i){
ele op,x,y,z;
scanf("%d%d%d",&op,&x,&y); --x;
if (op==1){
a[i]=y;
upd(root,0,n-1,dfn[x],dfn[x]+size[x]-1,i);
}
else if (op==2){
--y; scanf("%d",&z);
a[i]=z;
ele w=lca(x,y);
upd(x,w,i); upd(y,w,i);
upd(root,0,n-1,dfn[w],dfn[w],i);
}
}
memset(res,0,sizeof(res));
dfs3(root);
for (int i=0; i<Q; ++i) printf("%d\n",res[i]);
return 0;
}