bzoj 2741
2024-10-09 22:42:17
题目描述:这里
一道非常好的题
由于强制在线,我们必须要用一些数据结构来处理
考虑分块:将整个序列分块,块内部分预处理,块外部分暴力处理
对于每个块,计算出以这个块的左端点为端点,向右枚举这个块以后的所有点,然后记录下这样一个区间的最大异或值
然后每次查询的时候直接调用即可
#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 ;
}
最新文章
- 【Network】高性能 UDP 应该怎么做?
- (实用篇)浅谈PHP拦截器之__set()与__get()的理解与使用方法
- iOS xcode6 设置多语言
- Dynamic CRM 2015学习笔记 系列汇总
- Leetcode#56 Merge Intervals
- PHP学习笔记02——简易计算器
- asp.net中Repeater控件用法笔记
- iOS sharedSDK详解
- Hibernate的批量处理
- 视频媒体播放,最好的 HTML 解决方法
- Spark调研笔记第2篇 - 怎样通过Sparkclient向Spark提交任务
- 利用WebBrowser彻底解决Web打印问题
- WebApi client 的面向切面编程
- C实现dos图文菜单程序实例
- python内建函数isinstance基础用法
- java工厂设计模式初步
- httpd基础配置和虚拟主机的配置方法
- PAT (Basic Level) Practice (中文)1023 组个最小数
- 准备开发一个运行在Android上的JavaME模拟器
- vue中使用ueditor富文本编辑框
热门文章
- sprigboot recontroller 是responsebody与controller结合 这样 就使每个方法默认返回json
- [powershell]获取FCID&;Port
- [BJOI2017]树的难题
- ACM-ICPC 2018 徐州赛区网络预赛 HRyuji doesn&#39;t want to study 树状数组
- java并发编程 | 锁详解:AQS,Lock,ReentrantLock,ReentrantReadWriteLock
- (十五)qt-tcp
- (十四)QFile操作,QByteArray,文件流操作,QTextStream,QDataStream,QFileInfo, QIODevice
- 关于Mac 系统mysql 乱码问题
- 装饰器模式-Decorator(Java实现)
- NIPS2017-The neural hawks process