NKOJ8493 最大连续异或和

Problem

给定一个长度为\(N\)的非负整数数列
有个\(M\)询问，询问格式为\(L,R\),表示询问区间\([L,R]\)内的最大的连续异或和。
即求出\(max( A_i \ xor \ A_{i+1} \ xor \ A_{i+2} \ xor \ ... \ xor \ A_j )\) 其中\((L \leq i \leq j \leq R)\)

强制在线

\(1 \leq N \leq 12000,1 \leq M \leq 6000,1 \leq A_i \leq 2^{31}-1\)

Solution

分析题目性质，因为异或\((xor)\)操作有自反性，所以可以用前缀异或和来维护一段连续异或和，即\([l,r]\)异或和\(=sum[r]\ xor \ sum[l-1]\)

那么此题就被转换成了求区间\([L,R]\)的最大的\(sum[j]\ xor\ sum[i-1] \ (L \leq i \leq j \leq R)\)

显然这个问题可以用\(dp\)来做

\(f[i][j]:\)区间\([i,j]\)内任意两数异或之和最大
\(f[i][j]=max(f[i][j-1],sum[l]\)^\(sum[j])\ (i \leq l < j)\)

时间复杂度\(O(n^3)\)，爆炸，考虑优化

发现\(sum[l]\)^\(sum[j]\)相当于是从\([i,j)\)中找一个数异或上\(sum[j]\)最大，考虑可持久化\(01trie\)计算，时间复杂度被优化到了\(O(n^2logn)\)，可依然要炸。

那么直接考虑可持久化\(01trie\)，暴力枚举\(i\)，在\(trie\)上找异或\(sum[i]\)最大的\(sum[j]\)，单次询问时间复杂度\(O(nlogn)\)，有\(M\)次询问，也要炸。

注意到\(1 \leq N \leq 12000\)，考虑将\(N\)个前缀异或和分块，对每一块进行预处理\(f\)数组，然后询问时暴力查询不是块的部分，是完整块的直接用事先预处理好的即可。

详细的说呢，就是
\(f[i][j]:\)从第\(i\)块开头到第\(j\)块结尾这一段里任意两个数异或最大值
\(f[i][j]=max(f[i][j-1],sum[l]\)^\(sum[k])\)
\(l\)枚举\(j\)块内元素，\(k\)枚举的是\(i\)到\(j-1\)块的元素。
发现这里同样可以跟上面一样用可持久化\(01trie\)优化，于是时间复杂度变成了\(O((\sqrt n)^3logn) = O(n\sqrt nlogn)\)

对于每次询问时间复杂度\(O(2\sqrt nlogn)\)。
预处理空间复杂度\(O(n)\)，\(trie\)树\(O(nlogn)\)

\(code:\)

#include
using namespace std;
const int MAX_N = 15000 + 5;
const int MAX_S = 200 + 5;
typedef long long ll;
int n,m,s,tot,sum[MAX_N];
ll f[MAX_S][MAX_S],lastans,a[MAX_N];
inline int calc(int x){return (x-1)/s+1;}
int root[MAX_N];
struct PTrie{
	int num;
	int nxt[2];
}Ptrie[MAX_N * 32];
void Pins(ll x,int id){
	root[id]=++tot;
	int p=root[id],q=root[id-1];
	for(int i=30;i>=0;i--){
		int c=(x>>i)&1;
		for(int j=0;j<2;j++)
			Ptrie[p].nxt[j]=Ptrie[q].nxt[j];
		Ptrie[p].num=Ptrie[q].num+1;
		Ptrie[p].nxt[c]=++tot;
		p=Ptrie[p].nxt[c];
		q=Ptrie[q].nxt[c];
	}
	Ptrie[p].num=Ptrie[q].num;
	Ptrie[p].num++;
}
ll Pask(ll x,int a,int b){
	int q=root[a-1],p=root[b];
	ll ans=0;
	for(int i=30;i>=0;i--){
		int c=(x>>i)&1;
		int ps=Ptrie[p].nxt[c^1],qs=Ptrie[q].nxt[c^1];
		if(Ptrie[ps].num-Ptrie[qs].num>=1){
			ans|=(1ll<r) swap(l,r);
        lastans=query(l-1,r);
        printf("%lld\n",lastans);
    }
    return 0;
}

原文：https://www.cnblogs.com/TheAutumnGlory/p/15260781.html