NKOJ8493 最大连续异或和
2021/9/13 6:05:21
本文主要是介绍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<bits/stdc++.h> 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<<i); p=ps; q=qs; } else{ p=Ptrie[p].nxt[c]; q=Ptrie[q].nxt[c]; } } return ans; } ll query(int l,int r){ int kl=calc(l),kr=calc(r); ll ans=0; if(kl==kr){ for(int i=l;i<=r;i++){ ans=max(ans,Pask(sum[i],l,i)); } } else{ ans=0; if(kl+1<=kr-1) ans=f[kl+1][kr-1]; for(int i=l;i<=kl*s;i++) ans=max(ans,Pask(sum[i],l,r)); for(int i=(kr-1)*s+1;i<=r;i++) ans=max(ans,Pask(sum[i],l,r)); } return ans; } int main(){ // freopen("data.in","r",stdin); // freopen("data.out","w",stdout); scanf("%d%d",&n,&m); s=sqrt(n); Pins(sum[0],0); for(int i=1;i<=n;i++){ scanf("%lld",&a[i]); sum[i]=sum[i-1]^a[i]; Pins(sum[i],i); } for(int i=1;i<=calc(n);i++){ for(int j=i;j<=calc(n);j++){ ll maxn=0; for(int l=(j-1)*s+1;l<=j*s;l++) maxn=max(maxn,Pask(sum[l],(i-1)*s+1,l)); f[i][j]=max(f[i][j-1],maxn); } } while(m--){ ll x,y; scanf("%lld%lld",&x,&y); ll l=(x+lastans)%n+1; ll r=(y+lastans)%n+1; if(l>r) swap(l,r); lastans=query(l-1,r); printf("%lld\n",lastans); } return 0; }
这篇关于NKOJ8493 最大连续异或和的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-30我的第一个Go命令行工具
- 2024-09-30初学者指南:轻松掌握模块化编程
- 2024-09-30顶级5款免费的IntelliJ插件,助你Java开发之路更顺畅
- 2024-09-30提高应用程序可用性:冗余和持久性
- 2024-09-30Twitter 系统设计面试示例
- 2024-09-30JSON对象入门教程:轻松掌握基础用法
- 2024-09-30封装入门:Java面向对象编程的第一步
- 2024-09-30后台交互入门:轻松掌握基础知识与实践技巧
- 2024-09-30轻松入门:后台交互教程详解
- 2024-09-30后台交互项目实战:新手指南