HDU6579系列题解

2024年5月1日 互联网

题目链接

题目大意：

给你一个长度为n的数列，有m次操作，操作有两种：

  1. 在数列末尾插入一个数
  2. 查询区间的子集异或最大值

操作强制在线，n ≤ \le ≤ 5e5，m ≤ \le ≤ 5e5，所有数值域[0, 2 30 2^{30} 230]。

难度：Ag

分析：

线性基可以处理的操作是：

  1. 在数列末尾插入一个数
  2. 查询全局的子集异或最大值

由于线性基的长度很短，因此我们可以将数列所有前缀的线性基保存下来。1到x的线性基可以由1到x-1的线性基通过插入a[x]来求得，这样，我们就可以查询前缀区间的子集异或最大值。现在问题的关键在于，查询区间 [L, R] 时，如何避免 [1, L-1] 的干扰。

考虑线性基的插入过程，如果线性基当前位上已经有值，我们就不能把待插入的值放入这一位，因此线性基上每一位的数，都是对应位上在原数列最左侧的数字。现在我们改变策略，使得线性基上每一位的数，都变成对应位上在原数列最右侧的数字。实现这个策略的方法是：我们额外保存线性基上每一位数在原数列中的位置，插入的时候，如果对应位上的数在原数列中更靠左，就用待插入的数和它交换。基于这种策略，我们在查询区间 [L, R] 时，可以在区间 [1, R] 对应的线性基中查询，对于线性基上每一位的数，如果它在原数组中出现的位置比 L 更靠右，就考虑它对答案的贡献，否则直接跳过这一位。

这个做法的正确性也很显然，通过改变策略，使线性基上每一位数变成对应位上在原数列最右侧的数字，可以看成线性基插入数字的顺序变反，完全不影响线性基的性质。同时，将线性基上所有在原数组中的位置比 x 更靠左的数字删除，可以视为区间 [1, L-1] 的数字还没有被插入线性基。

复杂度：O((n + m) logx)，n为初始数列长度，m为操作次数，x为值域大小。

代码：

# include <bits/stdc++.h>
# define MAXN 1000005
# define MAXM 35using namespace std;struct LB
{int n;	//当前已插入的数字个数int a[MAXN][MAXM];	//保存所有前缀区间的线性基int b[MAXN][MAXM
最新文章