题目描述
小粽是一个喜欢吃粽子的好孩子。今天她在家里自己做起了粽子。
小粽面前有 nnn 种互不相同的粽子馅儿，小粽将它们摆放为了一排，并从左至右编号为 111 到 nnn。第 iii 种馅儿具有一个非负整数的属性值 aia_iai。每种馅儿的数量都足够多，即小粽不会因为缺少原料而做不出想要的粽子。小粽准备用这些馅儿来做出 kkk 个粽子。
小粽的做法是：选两个整数数 l,rl,rl,r，满足 1≤l≤r≤n1\le l\le r\le n1≤l≤r≤n，将编号在 [l,r][l,r][l,r] 范围内的所有馅儿混合做成一个粽子，所得的粽子的美味度为这些粽子的属性值的异或和。（异或就是我们常说的 xor\mathrm{xor}xor 运算，即 C/C++ 中的 ^ 运算符或 Pascal 中的 xor 运算符）
小粽想品尝不同口味的粽子，因此它不希望用同样的馅儿的集合做出一个以上的粽子。
小粽希望她做出的所有粽子的美味度之和最大。请你帮她求出这个值吧！ 输入格式
从标准输入读入数据。
第一行两个正整数 n,kn,kn,k，表示馅儿的数量，以及小粽打算做出的粽子的数量。
接下来一行为 nnn 个非负整数，第 iii 个数为 aia_iai，表示第 iii 个粽子的属性值。 输出格式
输出到标准输出。
输出一行一个整数，表示小粽可以做出的粽子的美味度之和的最大值。 样例 样例输入 1
3 2 1 2 3
样例输出 1
6
样例说明
小粽可以选取 [3,3],[1,2][3,3],[1,2][3,3],[1,2] 两个区间的馅儿做成粽子，两个粽子的美味度都为 333，和为 666。可以证明不存在比这更优的方案。 样例 2
见附加文件 2.in/ans。 数据范围与提示 测试点 nnn kkk 1∼81\sim 81∼8 ≤103\le 10^{3}≤103 ≤103\le 10^{3}≤103 9∼129\sim 129∼12 ≤5×105\le 5 \times 10^{5}≤5×105 ≤103\le 10^{3}≤103 13∼1613\sim 1613∼16 ≤103\le 10^{3}≤103 ≤2×105\le 2 \times 10^{5}≤2×105 17∼2017\sim 2017∼20 ≤5×105\le 5 \times 10^{5}≤5×105 ≤2×105\le 2 \times 10^{5}≤2×105
对于所有的输入数据都满足：1≤n≤5×105,1≤k≤min{n(n−1)2,2×105},0≤ai≤4,294,967,2951\le n \le 5 \times 10^{5},1\le k\le \min\left{\frac{n(n-1)}{2},2 \times 10^{5}\right},0\le a_i \le 4,294,967,2951≤n≤5×105,1≤k≤min{2n(n−1),2×105},0≤ai≤4,294,967,295。 来源
十二省联考 2019 题解： 亏死。 首先把区间异或转化为前缀异或。 前k大的做法：每个区间先取最大，再用堆维护取堆顶的次大值。执行k次即为答案。 如何查找区间k大呢那就是可持久化trie树。
注意注意注意： 位运算1<<x在long long 必用1LL<<x; 位运算1<<x在long long 必用1LL<<x; 位运算1<<x在long long 必用1LL<<x; 不然就爆0
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #include<cmath> #include<queue> #define N 500005 using namespace std; long long n,k,a[N],d[N]; long long tot,t[N*40][2],sum[N*40],root[N]; priority_queue<pair<long long, long long> > q; long long now[N]; long long search(long long p,long long x,long long limi){ long long ans=0; for(long long i=31;i>=0;--i){ long long ch=(x>>i)&1; if(t[p][ch^1]&&sum[t[p][ch^1]]>=limi){ p=t[p][ch^1];ans|=1LL<<i; }else{ limi-=sum[t[p][ch^1]];p=t[p][ch]; } //cout<<p<<" "<<limi<<endl; //cout<<p<<" "<<ans<<" "<<limi<<endl; if(p==0)return 0; } return ans; } void add(long long biao,long long x){ root[biao]=++tot; //cout<<biao<<":"<<endl; long long p=tot,pre=root[biao-1]; for(long long i=31;i>=0;--i){ long long ch=(x>>i)&1; t[p][1]=t[pre][1]; t[p][0]=t[pre][0]; sum[p]=sum[pre]+1; //cout<<p<<" "<<t[p][0]<<" "<<t[p][1]<<" "<<sum[p]<<endl; t[p][ch]=++tot; p=t[p][ch];pre=t[pre][ch]; } sum[p]=sum[pre]+1; //cout<<p<<" "<<sum[p]<<endl; } void build(){ long long p=root[0]; for(long long i=31;i>=0;--i){ sum[p]=1; t[p][0]=++tot; p=t[p][0]; } sum[p]=1; } int main() { scanf("%lld%lld",&n,&k); for(long long i=1;i<=n;++i){ scanf("%lld",&a[i]); d[i]=d[i-1]^a[i]; } root[0]=1;tot=1; build(); for(long long i=1;i<=n;++i){ q.push(make_pair(search(root[i-1],d[i],1),i)); add(i,d[i]); now[i]=1; } long long ans=0; while(k&&q.size()){k--; long long x=q.top().second;ans=ans+q.top().first; //cout<<q.top().second<<" "<<q.top().first<<endl; q.pop(); if(now[x]==x){continue;} q.push(make_pair(search(root[x-1],d[x],++now[x]),x)); } // add(1,d[1]);add(2,d[2]);add(3,d[3]);sum[0]=0;cout<<search(root[2],d[3],2)<<endl; printf("%lld\n",ans); return 0; }