题目描述:这里

一道非常好的题

由于强制在线,我们必须要用一些数据结构来处理

考虑分块:将整个序列分块,块内部分预处理,块外部分暴力处理

对于每个块,计算出以这个块的左端点为端点,向右枚举这个块以后的所有点,然后记录下这样一个区间的最大异或值

然后每次查询的时候直接调用即可

#include <cmath>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#define ll long long
using namespace std;
struct Trie
{
int to[];
int ed;
}tree[];
struct node
{
ll v;
int rq;
int num;
friend bool operator < (node a,node b)
{
return a.v<b.v;
}
};
priority_queue <node> M;
int rt[];
ll a[];
int n,k;
int tot=;
void ins(ll x,int now,int las)
{
rt[now]=++tot;
now=rt[now],las=rt[las];
for(int i=;i>=;i--)
{
tree[now]=tree[las];
tree[now].ed++;
if((x>>i)&)tree[now].to[]=++tot,now=tree[now].to[],las=tree[las].to[];
else tree[now].to[]=++tot,now=tree[now].to[],las=tree[las].to[];
}
tree[now].ed=tree[las].ed+;
}
ll query(int lq,int rq,ll x,int rk,int temp)
{
if(temp==-)return ;
int t=((x>>temp)&)?:;
int sum=tree[tree[rq].to[t]].ed-tree[tree[lq].to[t]].ed;
if(sum>=rk)return query(tree[lq].to[t],tree[rq].to[t],x,rk,temp-)+(1ll<<temp);
else return query(tree[lq].to[t^],tree[rq].to[t^],x,rk-sum,temp-);
}
int main()
{
scanf("%d%d",&n,&k);
n++;
ins(,,);
for(int i=;i<=n;i++)scanf("%lld",&a[i]),a[i]^=a[i-],ins(a[i],i,i-);
for(int i=;i<=n;i++)M.push((node){query(rt[],rt[i],a[i],,),i,});
ll ans=;
for(int i=;i<=k;i++)
{
node temp=M.top();
M.pop();
ans+=1ll*temp.v;
if(temp.num<temp.rq)M.push((node){query(rt[],rt[temp.rq],a[temp.rq],temp.num+,),temp.rq,temp.num+});
}
printf("%lld\n",ans);
return ;
}

最新文章

  1. 【Network】高性能 UDP 应该怎么做?
  2. (实用篇)浅谈PHP拦截器之__set()与__get()的理解与使用方法
  3. iOS xcode6 设置多语言
  4. Dynamic CRM 2015学习笔记 系列汇总
  5. Leetcode#56 Merge Intervals
  6. PHP学习笔记02——简易计算器
  7. asp.net中Repeater控件用法笔记
  8. iOS sharedSDK详解
  9. Hibernate的批量处理
  10. 视频媒体播放,最好的 HTML 解决方法
  11. Spark调研笔记第2篇 - 怎样通过Sparkclient向Spark提交任务
  12. 利用WebBrowser彻底解决Web打印问题
  13. WebApi client 的面向切面编程
  14. C实现dos图文菜单程序实例
  15. python内建函数isinstance基础用法
  16. java工厂设计模式初步
  17. httpd基础配置和虚拟主机的配置方法
  18. PAT (Basic Level) Practice (中文)1023 组个最小数
  19. 准备开发一个运行在Android上的JavaME模拟器
  20. vue中使用ueditor富文本编辑框

热门文章

  1. sprigboot recontroller 是responsebody与controller结合 这样 就使每个方法默认返回json
  2. [powershell]获取FCID&amp;Port
  3. [BJOI2017]树的难题
  4. ACM-ICPC 2018 徐州赛区网络预赛 HRyuji doesn&#39;t want to study 树状数组
  5. java并发编程 | 锁详解:AQS,Lock,ReentrantLock,ReentrantReadWriteLock
  6. (十五)qt-tcp
  7. (十四)QFile操作,QByteArray,文件流操作,QTextStream,QDataStream,QFileInfo, QIODevice
  8. 关于Mac 系统mysql 乱码问题
  9. 装饰器模式-Decorator(Java实现)
  10. NIPS2017-The neural hawks process