codefroces 1100 F. Ivan and Burgers(前缀线性基)

codefroces 1100 F. Ivan and Burgers(前缀线性基)

传送门

题意：

给出一个长度为 n n n的数组，有 q q q次查询，每次查询给出一个区间 [ l , r ] [l,r] [l,r] , 求区间内一些数异或和的最大值。

题解：

求异或和最大，可以想到线性基，那么怎么求区间内异或最大呢？

考虑给每个前缀维护一个线性基，对于一个新加进来的数，我们跟普通的线性基一样去处理它，但其中还要做一点改变。

设 p r e [ i ] [ j ] pre[i][j] pre[i][j] 表示前 i i i 个数组成的线性基中，第 j j j 位的数在数组中的位置，那么我们就需要尽量让 p r e [ i ] [ j ] pre[i][j] pre[i][j] 尽可能的大，即尽可能的往后，那么在查询的时候，只需要看 p r e [ i ] [ j ] ≥ l pre[i][j] geq l pre[i][j]≥l的位置即可，同时也保证了不会漏掉某个情况。

那么在插入新的数时，我们只需判断当前下标是否大于 p r e [ i ] [ j ] pre[i][j] pre[i][j] ,然后交换这两个数即可。

代码：

#pragma GCC diagnostic error "-std=c++11"
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#define iss ios::sync_with_stdio(false)
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
const int mod = 1e9 + 7;
const int MAXN = 5e5 + 5;
const int inf = 0x3f3f3f3f;
int pre[MAXN][31];
int dp[MAXN][31];
int a[MAXN];
struct node {int l, r;/* data */
} f[MAXN];
bool cmp(node x, node y)
{return x.r < y.r;
}
void insert(int x, int id)
{for (int i = 30; i >= 0; i--)pre[id][i] = pre[id - 1][i], dp[id][i] = dp[id - 1][i];int temp = id;for (int i = 30; i >= 0; i--) {if ((1 << i) & x) {if (!pre[id][i]) {pre[id][i] = temp;dp[id][i] = x;break;} else {if (temp > pre[id][i]) {swap(x, dp[id][i]);swap(temp, pre[id][i]);}x ^= dp[id][i];}}}
}
int main()
{int n;scanf("%d", &n);for (int i = 1; i <= n; i++) {scanf("%d", &a[i]);}int q;scanf("%d", &q);for (int i = 1; i <= q; i++) {scanf("%d%d", &f[i].l, &f[i].r);}//sort(f + 1, f + 1 + q, cmp);for (int i = 1; i <= n; i++) {insert(a[i], i);}for (int i = 1; i <= q; i++) {int ans = 0;for (int j = 30; j >= 0; j--) {if (pre[f[i].r][j] >= f[i].l) {if ((ans ^ dp[f[i].r][j]) > ans) {ans ^= dp[f[i].r][j];}}}printf("%dn", ans);}
}