CF1100F Ivan and Burgers

给定\(n\)和\(a_{1\cdots n}\)，有\(q\)个询问，每个询问要求区间\([l,r]\)内选出任意个数的异或最大值。\((n,q\leq 5\times 10^5, a_i\leq 10^6)\)

不知道怎么就想到了分块。先按\(\sqrt n\)分块，预处理出\(f[l][r]\)表示第\(l\)个块到第\(r\)个块所有数的线性基，这个可以\(\mathcal O(nlog^2a)\)算出来。

然后我们还可以处理出\(pre[x][i]\)表示第\(x\)个块的第\(1\) ~ \(i\)个数组成的线性基，类似地有\(suf[x][i]\)表示第\(x\)个块的第\(i\) ~ \(\sqrt n\)个数组成的线性基。

对于每个询问，我们可以把它包含的所有完整的块直接通过\(f\)数组加进答案的线性基里，然后再通过\(pre\)和\(suf\)数组把不完整的加进答案的线性基里。

最后对于每个询问的线性基，贪心地求最大值即可。时间复杂度\(\mathcal O((n+q)log^2a)\)

#include<bits/stdc++.h>
#define rg register
#define il inline
#define cn const
#define gc getchar()
#define fp(i, a, b) for(rg int i = (a), ed = (b); i <= ed; ++i)
#define fb(i, a, b) for(rg int i = (a), ed = (b); i >= ed; --i)
#define go(u) for(int i = head[u]; ~i; i = e[i].nxt)
using namespace std;
typedef cn int cint;
typedef long long LL;
typedef pair<int, int> pr;
il void rd(int &x){
	x = 0;
	rg int f(1); rg char c(gc);
	while(c < ‘0‘ || ‘9‘ < c){if(c == ‘-‘)f = -1; c = gc;}
	while(‘0‘ <= c && c <= ‘9‘)x = (x<<1)+(x<<3)+(c^48), c = gc;
	x *= f;
}
cint maxn = 500010, maxm = 710;
int n, cnt, m, unit, a[maxn], col[maxn];
struct query{int l, r;}q[maxn];
vector<pr> qry[maxn<<2];
struct base{int v[20];}f[maxm][maxm], ans[maxn], pre[maxm], suf[maxm];
il void add(base &a, int x){
	fb(i, 19, 0)if(x>>i&1){
		if(!a.v[i])return a.v[i] = x, void();
		x ^= a.v[i];
	}
}
il void merge(base &a, cn base &b){fp(i, 0, 19)add(a, b.v[i]);}
int main(){
	rd(n), unit = sqrt(n);
	fp(i, 1, n)rd(a[i]);
	for(rg int l = 1; l<=n; l += unit, ++cnt){
		rg int r = min(n, l+unit-1);
		fp(j, l, r)add(f[cnt][cnt], a[j]), col[j] = cnt;
	}
	--cnt;
	fb(i, cnt-1, 0)fp(j, i+1, cnt)f[i][j] = f[i+1][j], merge(f[i][j], f[i][i]);
	rd(m);
	fp(i, 1, m){
		rd(q[i].l), rd(q[i].r);
		if(col[q[i].l] == col[q[i].r]){
			fp(j, q[i].l, q[i].r)add(ans[i], a[j]);
			continue;
		}
		qry[col[q[i].l]].push_back(make_pair(i, 0));
		qry[col[q[i].r]].push_back(make_pair(i, 1));
		if(col[q[i].r]-col[q[i].l] > 1)merge(ans[i], f[col[q[i].l]+1][col[q[i].r]-1]);
	}
	for(rg int l = 1, nw = 0; l<=n; l += unit, ++nw){
		rg int r = min(n, l+unit-1);
		fp(j, l, r)pre[j-l+1] = pre[j-l], add(pre[j-l+1], a[j]);
		fb(j, r, l)suf[j-l+1] = suf[j-l+2], add(suf[j-l+1], a[j]);
		for(auto &x : qry[nw]){
			if(!x.second)merge(ans[x.first], suf[q[x.first].l-l+1]);
			else merge(ans[x.first], pre[q[x.first].r-l+1]);
		}
	}
	fp(i, 1, m){
		rg int res = 0;
		fb(j, 19, 0)if(ans[i].v[j] && !(res>>j&1))res ^= ans[i].v[j];
		printf("%d\n", res);
	}
	return 0;
}

CF1100F Ivan and Burgers

原文：https://www.cnblogs.com/akura/p/14407432.html