可持久化$Trie$

学可持久化$Trie$啦,我们先看这道题——最大异或和(传送门
题目描述
给定一个非负整数序列$\{a\}{}$,初始长度为$N$。

有$M$个操作,有以下两种操作类型:

$A x$:添加操作,表示在序列末尾添加一个数 $x$,序列的长度$N+1$.
$Q$ $l r x$:询问操作,你需要找到一个位置 $p$,满足$l \le p \le r$,使得: 最大,输出最大是多少。
输入格式
第一行包含两个整数 $N$,$M$,含义如问题描述所示。
第二行包含 $N$个非负整数,表示初始的序列 $A$。
接下来 $M$行,每行描述一个操作,格式如题面所述。

输出格式
假设询问操作有 $T$ 个,则输出应该有 $T$ 行,每行一个整数表示询问的答案。


有一个序列 $A$ ,每次可以进行两种操作,一是在序列尾插入一个数,序列长度 $N$ 变为 $N+1$ ,二是在区间 $[l,r]$ 中找到一个 $p$ ,满足 $l≤p≤r$,并使得 $A[p]\oplus A[p+1]\oplus…\oplus A[N]\oplus xA[p]⊕A[p+1]⊕…⊕A[N]⊕x$ 最大,输出这个最大值。

首先,我们把这个式子拆开,也就变成了 ,似乎很简单,但是这道题还有一个在末尾插入的操作,就需要我们用到可持久化$Trie$了。

其实可持久化$Trie$和主席树的思想是类似的,实现方式也有相同之处,就是对每一个前缀异或建一个$01Trie$,该继承的继承,该修改的修改,这样就完成了。

插入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void insert(int x)
{
int rt=root[node_cnt]; //取出上一个根节点的信息
root[++node_cnt]=++node; //新建节点
for (register int i=24;i>=0;i--)
{
int ch=(x>>i)&1; //取出
size[node]=size[rt]+1; //长度增加
trie[node][ch]=node+1; //给节点编号
trie[node][!ch]=trie[rt][!ch]; //继承上一个根节点的部分子树信息
rt=trie[rt][ch]; //往下走
node++;
}
size[node]=size[rt]+1;
}

访问

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void query(int l,int r,int x)
{
int lc=root[l],rc=root[r],ans=0; //取出左右子树
for (register int i=24;i>=0;i--)
{
int ch=(x>>i)&1; //取出
if (size[trie[rc][!ch]]-size[trie[lc][!ch]]>0)
//如果反路有路可走
lc=trie[lc][!ch],rc=trie[rc][!ch],ans|=1<<i;
//走反路并更新答案
else
lc=trie[lc][ch],rc=trie[rc][ch];
//否则只能往下走
}
write(ans);
putchar(10);
}

时空复杂度:总共: $O(31(N+M))$

$AC$代码

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
// luogu-judger-enable-o2
#include <bits/stdc++.h>

using namespace std;
const int maxn = 2*1e7;
int root[maxn], node_cnt, node, size[maxn];
int trie[maxn][3];

int n, m;

inline int read() {
int x(0), w(0);
char ch(0);
//ch = getchar();
while (!isdigit(ch)) w |= ch == '-', ch = getchar();
while (isdigit(ch))
x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
return w ? -x : x;
}

inline void write(int x) {
if (x < 0) putchar('-'), x = -x;
if (x > 9) write (x / 10);
putchar(x % 10 + '0');
}

inline void insert(int x) {
int rt = root[node_cnt];
root[++node_cnt] = ++node;
for (register int i = 24; i >= 0; i--) {
int ch = (x >> i) & 1;
size[node] = size[rt] + 1;
trie[node][ch] = node + 1;
trie[node][!ch] = trie[rt][!ch];
rt = trie[rt][ch];
node++;
}
size[node] = size[rt] + 1;
}

inline void query(int l, int r, int x) {
int lc = root[l], rc = root[r], ans = 0;
for (register int i = 24; i >= 0; i--) {
int ch = (x >> i) & 1;
if (size[trie[rc][!ch]] - size[trie[lc][!ch]] > 0)
lc = trie[lc][!ch], rc = trie[rc][!ch], ans |= 1 << i;
else
lc = trie[lc][ch], rc = trie[rc][ch];
}
write(ans);
putchar(10);
}
int getc(){
char ch = getchar();
while (ch<'A' || ch>'Z') ch =getchar();
return ch == 'A';
}
int main() {
n = read();
m = read();
int x, sum = 0;
insert(0);//一定别忘了加
for (register int i = 1; i <= n; i++)
x = read(), sum ^= x, insert(sum);
int l, r, z, ch;
for (register int i = 1; i <= m; i++) {
ch = getc();
if (ch == 1)
z = read(), sum ^= z, insert(sum);
else
l = read(),r = read(),z = read(),query(l-1,r,z^sum);

}
return 0;
}

后续知识前导题 序列合并

题意

两个长度都为$N$的序列$A$和$B$,各任取一个数共有$N^2$个和,求这些和中最小的$N$个。($N<=1e5$)

分析

首先,把$A$和$B$两个序列分别从小到大排序,变成两个有序队列。这样,从$A$和$B$中各任取一个数相加得到$N^2$个和,可以把这些和看成形成了$n$个有序表/队列:

接下来,就相当于要将这$N$个有序队列进行合并排序:

首先,将这$N$个队列中的第一个元素放入一个堆中;

然后;每次取出堆中的最小值。若这个最小值来自于第$k$个队列,那么,就将第k个队列的下一个元素放入堆中。

时间复杂度:$O(NlogN)$。

有了这道题做前导知识,就可以解决下面这个问题。


异或粽子(紫题Warning ) 传送门

题目描述

小粽是一个喜欢吃粽子的好孩子。今天她在家里自己做起了粽子。

小粽面前有 $n$ 种互不相同的粽子馅儿,小粽将它们摆放为了一排,并从左至右编号为 $1$ 到 $n$。第 $i$ 种馅儿具有一个非负整数的属性值 $a_i$ 。每种馅儿的数量都足够多,即小粽不会因为缺少原料而做不出想要的粽子。小粽准备用这些馅儿来做出 $k$ 个粽子。

小粽的做法是:选两个整数数 $l$ , $r$,满足 $1⩽l⩽r⩽n$,将编号在 $[l,r]$ 范围内的所有馅儿混合做成一个粽子,所得的粽子的美味度为这些粽子的属性值的异或和。(异或就是我们常说的 $xor$ 运算,即 C/C++ 中的 ˆ 运算符或 Pascal 中的 $xor$ 运算符)

小粽想品尝不同口味的粽子,因此它不希望用同样的馅儿的集合做出一个以上的粽子。

小粽希望她做出的所有粽子的美味度之和最大。请你帮她求出这个值吧!

分析

很显然 ,题目想让你求出长度为N序列的前k大的$A[l]⊕A[l+1]⊕…⊕Ar$ 区间异或和。$(N<=5e5)$
怎么考虑呢?
很显然可以构造前缀异或和数组 $sum$ ,那只需要找到前$k$对 $max(sum[i]⊕sumj)$ ,问题就解决了。
关键是怎么找到这前$k$对呢?
对于区间 $[L,R]$ 如果我们固定了右端点 $R$,在 $[0,R-1]$ 中找一个数异或$sum_r$ 最大,可以使用可持久化 $01Trie$ 解决,复杂度 $O(logN)$。
那我们把这 $n$ 个$sum$放到堆里。
每次取出最大的那个状态。设这个状态左端点在 $[l,r]$ ,与 $sum_x$
异或起来最大的位置在 $k$,那么我们把状态的左端点分割成 $[l,k−1]$ 和 $[k+1,r]$ 后放入堆中。
很多小盆友看到这里肯定会问:为什么要把这个状态拆分了??
删除一个数,剩下的所有后缀异或和都会异或上删掉的数,所以可以全局维护一个 $tag$,删一个数就用tag异或上它,在查询到tag上这个位上为1时就要反着走。
想到这里,突然有点其他的想法,对于类似的删除点或状态的问题对后面的都产生了影响(比如前缀和数组),如果顺序修改的话是$O(N)$的,不如考虑另外构建一个树状数组前缀和差分$tag$,修改和查询都做到$O(logN)$。

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
//代码来源题解
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=500000+10;
int n,k,rt[maxn],cnt;ll a[maxn],ans;

struct node
{
int ch[2],siz,id;
}t[maxn*40];

inline ll read()
{
register ll x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
return (f==1)?x:-x;
}

void insert(int &now,int pre,int bit,int id,ll val)
{
now=++cnt;t[now]=t[pre];t[now].siz++;
if(bit==-1){t[now].id=id;return;}
if((val>>bit)&1) insert(t[now].ch[1],t[pre].ch[1],bit-1,id,val);
else insert(t[now].ch[0],t[pre].ch[0],bit-1,id,val);
}

int query(int u,int v,int bit,ll val)
{
if(bit==-1) return t[v].id;
int d=(val>>bit)&1;
if(t[t[v].ch[d^1]].siz-t[t[u].ch[d^1]].siz>0) return query(t[u].ch[d^1],t[v].ch[d^1],bit-1,val);
return query(t[u].ch[d],t[v].ch[d],bit-1,val);
}

struct State
{
int l,r,x,id;ll val;
State(int _l=0,int _r=0,int _x=0)
{
l=_l;r=_r;x=_x;
id=query(rt[l-1],rt[r],31,a[x]);
val=a[x]^a[id-1];
}
};
inline bool operator < (const State &a,const State &b)
{
return a.val<b.val;
}
priority_queue<State> pq;

int main()
{
n=read(),k=read();
for(int i=1;i<=n;i++) a[i]=a[i-1]^read();
for(int i=1;i<=n;i++) rt[i]=rt[i-1],insert(rt[i],rt[i],31,i,a[i-1]);
for(int i=1;i<=n;i++) pq.push(State(1,i,i));
while(k--)
{
State u=pq.top();pq.pop();ans+=u.val;
if(u.l<u.id) pq.push(State(u.l,u.id-1,u.x));
if(u.id<u.r) pq.push(State(u.id+1,u.r,u.x));
}
printf("%lld\n",ans);
return 0;
}

理解还有不到位的地方,若以后遇到类似的再回头看看。