271.最大异或和
题目:
给定一个非负整数序列a,初始长度为N。有M个操作,有以下两种操作类型:
1、"A x":添加操作,表示在序列未尾添加一个数x,序列的长度N增大1。
2、"Q I r x":询问操作,你需要找到一个位置p,满足l≤p≤r,使得:a[p] xor a[p+1] xor...xor a[N] xor x最大,输出这个最大值。
输入格式
第一行包含两个整数N,M,含义如问题描述所示。第二行包含N个非负整数,表示初始的序列A。接下来M行,每行描述一个操作,格式如题面所述。
输出格式
每个询问操作输出一个整数,表示询问的答案。每个答案占一行。
数据范围
N,M≤3×10⁵
0≤a[i]≤10⁷
思路:
1.我们本节讲Trie的可持久化和线段树的可持久化,也就是主席树。一个数据结构想可持久化,前提就是这个数据结构本身的拓扑结构不变。比如线段树,里面的信息可能会发生改变,但是它的结构是不变的。平衡树一般来说不太容易支持可持久化,因为它在左旋或者右旋的时候结构会发生变化。如果数据结构想把所有历史版本都存下来,能够回滚,这时候就需要可持久化的数据结构了。如果每次修改后都全部备份一次的话,那空间复杂度和时间复杂度都是非常高的。它只会记录每一个版本和前一个版本不同的结点。
2.首先我们来看可持久化Trie。假设我们用Trie存了四个单词cat,rat,cab,fry。
上图即为可持久化Trie的样例。其中红色的代表每一个版本的Trie树,绿色代表克隆过来的点。我们每一次只记录和上版本比较来说新的部分。先把从根节点开始和原来的树中相同的原有的部分克隆过来,凡是中间有变化的都要裂开,并且一直裂到结尾,无论结尾相不相同。比如rat和cat,虽然后两个字母都是at,但是因为第一个字母就不相同,所以直接裂开走两条路。而aba和aca,因为第一个a相同,所以可以先复制过来a,但是第二个字母不同,此时就要裂开,即使最后一个字母都是a,也要裂开着写。
而根结点因为这里每次都是插入新的单词,所以我们要裂开。相当于每次裂出一个新路径。
2.Insert的时候,我们需要有一个指针指向上一个版本,即p=root[i-1]。注意,这里root[i-1]是上一版本的指向第一个结点的指针。
新的版本先开一个新的结点,即q=root[i]=++idx。
先看p是不是空的,如果是空的,就说明是全新的点不用管。如果不是空的,就先把p克隆过来,即if (p) tr[q]=tr[p]。注意,这里tr是存储每个结点的数组。我们解析的代码中定义的是tr[M][2],也就是左儿子就是tr[M][0],右儿子就是tr[M][1]。
其次,再把我们新的点当前的指针对应的点更新。假设它的儿子对应的符号是si,那么tr[q][si]=++idx。
然后p指向下一个位置,p=tr[p][si]。
q也指向下一个位置,q=tr[q][si]。
直到遍历完所有结点。
3.我们可以先考虑做一个前缀和。S0=0,S1=A1,S2=A1^A2……
那么Ap^……AN^x=Sp-1^SN^x,这里SN^x是一个固定的值,我们把它看成C。那么我们就是在L~R里,求出一个p,使得Sp-1 ^ C最大。
我们用一个Tire维护所有数,把每一个数看成一个24位的01串。然后放到Trie树里。
我们这里借鉴最大异或值那个题目里的贪心思想。假设我们的C是110010101……那么当我们的Sp-1里,如果包含最高位是0的,那么我们就一定需要去最高位为0的集合里去做异或。因为这样异或后最高位是1,最大。同理,次高位也是去次高位位0的集合里去选。而第三位就需要去第三位为1的集合里去选,只有这个集合为空的时候,才去第三位为0的集合里去选择。每次我们怎么判断是一是零存不存在呢?我们只需要判断左右子树是否为空即可。只要存在就过去,不存在去另一个子树。
4.这里如果只有右边的限制很好说,也就是1-R里选一个数,与C异或后最大。我们只要在以root[R]为根的这个版本的子树里搜就可以了,也就是第R个版本。但是左边的限制怎么办呢?如果限制是[L,R]的话,假设搜到了一个点,左子树是0,右子树是1,我们先搜左子树,那么我们要分析左边子树中是否至少存在一个数,它的下标大于等于L。如果左子树搜到了一个某一个数的下标大于等于L,那么就等价于左子树下标最大值一定大于等于L。
所以这就启发我们记录一个max_id,记录当前子树中下标的最大值。每次在递归的时候判断左子树是否存在下标大于等于L的结点,如果有,那就递归左子树就可以了,没有就递归另一边的子树。
5.如果Trie爆空间了,那么我们可以反推,从题目给的空间来反推,有多少就开多少结点。但是注意不能全部占满,因为程序本身还需要一些空间来运行。
6.注意,我们这里每个结点存的是异或后的值,而不是原始数值。
代码(c++):
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 600010, M = N * 25 //原始数据三十万个,再加上三十万个操作,每个操作假设最坏是插入,所以N设为600010。同理,我们的异或值最多有600001个,我们最多有24位,加上根节点,我们每次最多只会建立25个点。所以这里乘25,也就是表示最多有15000000个结点
int n, m;
int s[N]; //前缀异或值
int tr[M][2], max_id[M]; //tr里存的是结点编号,也就是Trie的连接关系。而max_id记录的是下标,而不是最大的异或值
int root[N], idx; //idx是当前已经建立了多少trie结点。
void insert(int i, int k, int p, int q) //前缀和下标,当前处理到第几位,上一个版本,最新版本
{
if (k < 0) //处理完了最后一位
{
max_id[q] = i; //说明是叶结点了
return;
}
int v = s[i] >> k & 1; //取出目前的前缀和的第k位,必须加&1,否则取出的不是最后一位
if (p) tr[q][v ^ 1] = tr[p][v ^ 1]; //这里的p是tr[p][v],也就是说只有当这条路径上是空的时候,才会不进行复制操作,如果不空,复制。假设v是0,那么0方向是需要变化的,因为插入了新的异或值。另一个方向,也就是1方向,直接复制指针
tr[q][v] = ++ idx; //当前路径一定是新的点
insert(i, k - 1, tr[p][v], tr[q][v]);
max_id[q] = max(max_id[tr[q][0]], max_id[tr[q][1]]); //递归计算max_id,先计算儿子才能知道父亲的,所以要放在递归的后面
}
int query(int root, int C, int L)
{
int p = root;
for (int i = 23; i >= 0; i -- )
{
int v = C >> i & 1;
if (max_id[tr[p][v ^ 1]] >= L) p = tr[p][v ^ 1]; //能走到这一步说明肯定是存在合法结点的,因为如果没有>=L的结点就会矛盾,正是因为有>=L的结点才会走到这个结点的。并且每次都先看相反位的,所以可以保证异或最大
else p = tr[p][v];
}
return C ^ s[max_id[p]];
}
int main()
{
scanf("%d%d", &n, &m);
max_id[0] = -1; //因为要算前缀和,带前缀和下标从0开始,0也是一个合法前缀和,所以根节点的max_id需要更小
root[0] = ++ idx;
insert(0, 23, 0, root[0]); //因为儿子算完才能算父亲的max_id,所以最好insert写成递归形式。第一个0是前缀和下标,也就是第一个前缀和。23代表总位数。第二个0是代表上一个版本为空,root[0]是当前版本
for (int i = 1; i <= n; i ++ )
{
int x;
scanf("%d", &x);
s[i] = s[i - 1] ^ x;
root[i] = ++ idx;
insert(i, 23, root[i - 1], root[i]); //从23位开始向前插
}
char op[2];
int l, r, x;
while (m -- )
{
scanf("%s", op);
if (*op == 'A')
{
scanf("%d", &x);
n ++ ;
s[n] = s[n - 1] ^ x;
root[n] = ++ idx;
insert(n, 23, root[n - 1], root[n]);
}
else
{
scanf("%d%d%d", &l, &r, &x);
printf("%d\n", query(root[r - 1], s[n] ^ x, l - 1)); //因为我们要选的是在1~p-1里的结点,所以是root[r-1],题目要求p≥l,而这里用的r-1,对应l-1
}
}
return 0;
}
272.第k小数
题目:
给定长度为N的整数序列A,下标为1~N。
现在要执行M次操作,其中第i次操作为给出三个整数lᵢ,rᵢ,kᵢ,求A[lᵢ],A[lᵢ+1],...,A[rᵢ](即A的下标区间[lᵢ,rᵢ])中第kᵢ小的数是多少。
输入格式
第一行包含两个整数N和M。
第二行包含N个整数,表示整数序列A。
接下来M行,每行包含三个整数lᵢ,rᵢ,kᵢ,用以描述第i次操作。
输出格式
对于每次操作输出一个结果,表示在该次操作中,第k小的数的数值。
每个结果占一行。
数据范围
N≤10⁵,M≤10⁴,|A[i]|≤10⁹
思路:
1.这题要用可持久化线段树,可持久化线段树就是主席树。思想类似可持久化trie,每一次修改都会存下来当前这个最新版本。假设一共有m次修改,线段树一共会存下来m+1个版本。修改和trie其实是一样的道理,只有一个结点信息发生变化的时候,那就会给它裂一个新的结点,没变的还用原来的。我们之前说过线段树每一次操作最多只会改变4logn个区间,一共m次,所以一共最多会创建新的O(mlogn)个区间。
2.因为之前是用堆操作的,而现在由于有多个版本,显然不可以用堆进行操作了。而是应该用指针。定义如下
struct{
int l , r; //表示左右子节点的下标
int cnt; //表示当前区间一共有多少个数
}
我们一般来说在用指针表示线段树的时候,就不用记录左右边界了,直接传递即可。
可持久化线段树难以进行区间修改操作,因为有很多版本,如果当前区间修改了,我只是把当前版本的懒标记下传了,但是前面还可能有很多版本包含这个点,那么那些历史版本的懒标记也是需要更新的。
不过有一种方法,就是把懒标记永久化,就可以处理了,这里不做讲解。
如图所示,每次操作的时候会修改某一条路径,那么把该路径删除,并用修改后的路径替代,原路径上的没被修改的结点被修改后的结点所指向。
3.这个题是一个非常经典的题目,首先它是一个静态问题,原数列在操作过程中是不变化的。如果用归并树,我们的时间复杂度是O(nlog³n),非常麻烦。如果用划分树,划分树只能解决区间第k小数问题,但是它的时间和空间复杂度都是O(nlogn)。还可以用树套树,也就是线段树套平衡树,以后做介绍,好处是可以支持修改,每次查询时间复杂度为O(mlog²n)。空间复杂度O(nlogn)。而本次我们采用可持久化线段树,时间和空间复杂度为O(nlogn)。
4.我们这里维护的不是下标,而是值域。因为数范围比较大,所以我们先离散化,离散化后,在数值上建立线段树。维护每个数值区间中一共有多少个数。如何求整体的第k小数?我们可以在线段树上做二分,因为这个树本身就是一个二叉树。假设现在一个线段树的结点被划分为(0,mid),(mid,n-1)两个区间。如果左边区间的cnt是≥k的,那么说明我们的第k小数一定是在左边区间的。否则在右边区间。所以最多只会访问logn个结点,时间复杂度为O(logn)。这是从1-n的情况,但是如果我们左边的起始点不是1的话,就不能这么做了。例如查询[L,R]区间的第k小数,因为线段树的每个版本结构都是一样的,只不过信息不同。所以我们可以用前缀和的思想,假设第R个版本里,某个结点[l,r]为cnt₁,第L-1个版本里,某个结点[l,r]为cnt₂。所以cnt₁-cnt₂就是结果,我们递归的时候同时递归两个版本,这样就可以成功求解,时间和空间复杂度都是O(nlogn)。
代码(c++):
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 100010, M = 10010;
int n, m;
int a[N];
vector<int> nums; //用于离散化
struct Node
{
int l, r;
int cnt;
}tr[N * 4 + N * 17]; //n次操作,需要nlogn个点,n为100000,所以开n*17,又因为线段树基础需要n*4,所以相加
int root[N], idx;
int find(int x)
{
return lower_bound(nums.begin(), nums.end(), x) - nums.begin(); //lower_bound本身是一个二分,用于二分查找有序区间内第一个不小于x的数,此处又减去了偏移量
}
int build(int l, int r)
{
int p = ++ idx; //建立新点
if (l == r) return p;
int mid = l + r >> 1;
tr[p].l = build(l, mid), tr[p].r = build(mid + 1, r);
return p;
}
int insert(int p, int l, int r, int x)
{
int q = ++ idx;
tr[q] = tr[p]; //先复制原来的结点
if (l == r)
{
tr[q].cnt ++ ; //区间数+1
return q;
}
int mid = l + r >> 1;
if (x <= mid) tr[q].l = insert(tr[p].l, l, mid, x);
else tr[q].r = insert(tr[p].r, mid + 1, r, x);
tr[q].cnt = tr[tr[q].l].cnt + tr[tr[q].r].cnt; //更新结点数量
return q;
}
int query(int q, int p, int l, int r, int k)
{
if (l == r) return r; //如果只有一个点,这个点就是答案
int cnt = tr[tr[q].l].cnt - tr[tr[p].l].cnt;
int mid = l + r >> 1;
if (k <= cnt) return query(tr[q].l, tr[p].l, l, mid, k);
else return query(tr[q].r, tr[p].r, mid + 1, r, k - cnt);
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ )
{
scanf("%d", &a[i]);
nums.push_back(a[i]);
}
sort(nums.begin(), nums.end());
nums.erase(unique(nums.begin(), nums.end()), nums.end());
root[0] = build(0, nums.size() - 1);
for (int i = 1; i <= n; i ++ )
root[i] = insert(root[i - 1], 0, nums.size() - 1, find(a[i])); //在前一个版本基础上比较,边界是[0,nums.size-1],find[a[i]]是我们找到的数对应的离散值,应该加上1
while (m -- )
{
int l, r, k;
scanf("%d%d%d", &l, &r, &k);
printf("%d\n", nums[query(root[r], root[l - 1], 0, nums.size() - 1, k)]);
}
return 0;
}

