最大异或和
https://zybuluo.com/ysner/note/1238161题面给定一个初始长度为(N)的非负整数序列({a})。
具体建立方法有点像把(Trie)树和主席树结合起来。 至于这个奇怪的询问方式,设异或前缀和为(S),则询问可视为(S_Nbigoplus S_{p-1})。 注意数组(rt,sum,t)等数组大小要开到(n*50)左右。 #include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<algorithm> #include<vector> #define re register #define il inline #define ll long long #define max(a,b) ((a)>(b)?(a):(b)) #define min(a,b) ((a)<(b)?(a):(b)) #define fp(i,a,b) for(re int i=a;i<=b;i++) #define fq(i,b) for(re int i=a;i>=b;i--) using namespace std; const int mod=1e9+7,N=3e7+100; int n,m,tot,sum[N],t[N][2],rt[N],tim; il ll gi() { re ll x=0,t=1; re char ch=getchar(); while(ch!=‘-‘&&(ch<‘0‘||ch>‘9‘)) ch=getchar(); if(ch==‘-‘) t=-1,ch=getchar(); while(ch>=‘0‘&&ch<=‘9‘) x=x*10+ch-48,ch=getchar(); return x*t; } il void Build(re int x,re int &y,re int w,re int d) { sum[y=++tim]=sum[x]+1; if(d<0) return; re int tmp=(w>>d)&1; t[y][tmp^1]=t[x][tmp^1]; Build(t[x][tmp],t[y][tmp],w,d-1); } il int Query(re int x,re int y,re int d) { if(d<0) return 0; re int tmp=(w>>d)&1,p=sum[t[y][tmp^1]]-sum[t[x][tmp^1]]; if(p>0) return (1<<d)+Query(t[x][tmp^1],t[y][tmp^1],d-1); else return Query(t[x][tmp],d-1); } int main() { n=gi();m=gi(); Build(rt[0],rt[1],25);++n; fp(i,2,n) { re int x=gi();tot^=x; Build(rt[i-1],rt[i],25); } while(m--) { re char s[5];scanf("%s",s); if(s[0]==‘A‘) { re int x=gi();tot^=x; Build(rt[n],rt[n+1],25);++n; } else { re int l=gi(),r=gi(),x=gi(); printf("%dn",Query(rt[l-1],rt[r],tot^x,25)); } } return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |