技术标签： 可持久化trie树 --------杂-------- --------数据结构-------- 贪心 bzoj
Welcome to ALO ( Arithmetic and Logistic Online)。这是一个VR MMORPG ，
如名字所见，到处充满了数学的谜题。
现在你拥有n颗宝石，每颗宝石有一个能量密度，记为ai，这些宝石的能量
密度两两不同。现在你可以选取连续的一些宝石（必须多于一个）进行融合，设为 ai, ai+1, …, a j，则融合而成的宝石的能量密度为这些宝石中能量密度的次大值
与其他任意一颗宝石的能量密度按位异或的值，即，设该段宝石能量密度次大值
为k，则生成的宝石的能量密度为max{k xor ap | ap ≠ k , i ≤ p ≤ j}。
现在你需要知道你怎么选取需要融合的宝石，才能使生成的宝石能量密度最大。
第一行，一个整数 n，表示宝石个数。
第二行， n个整数，分别表示a1至an，表示每颗宝石的能量密度，保证对于i ≠ j有 ai ≠ aj。
输出一行一个整数，表示最大能生成的宝石能量密度。
5
9 2 1 4 7
14
【样例解释】
选择区间[1,5]，最大值为 7 xor 9。
对于 100%的数据有 1 ≤ n ≤ 50000, 0 ≤ ai ≤ 10^9
按贪心的思路，肯定是考虑每个数能作为次大值的最大区间。
可以发现每个数的最大区间就是在他前面第二个比它大的数到在他后面第二个比它大的数，直接从大到小插入，用set维护前驱后继位置即可。
然后上可持久化trie树按位贪心找就可以了。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int getint()
{
int i=0,f=1;char c;
for(c=getchar();(c!='-')&&(c<'0'||c>'9');c=getchar());
if(c=='-')f=-1,c=getchar();
for(;c>='0'&&c<='9';c=getchar())i=(i<<3)+(i<<1)+c-'0';
return i*f;
}
const int N=50005,INF=0x3f3f3f3f;
struct node{
int cnt,son[2];}tr[N*35];
struct node1{
int val,pos;}a[N];
inline bool operator < (const node1 &a,const node1 &b){
return a.val>b.val;}
int n,tot,ans,rt[N];
set<int>S;
set<int>::iterator it1,it2;
void Insert(int y,int &x,int v,int dep)
{
tr[x=++tot]=tr[y],tr[x].cnt++;
if(dep<0)return;
int t=(v>>dep)&1;
Insert(tr[y].son[t],tr[x].son[t],v,dep-1);
}
int query(int x,int y,int v,int res,int dep)
{
if(dep<0)return res;
int t=(v>>dep)&1,dl=tr[tr[x].son[t^1]].cnt,dr=tr[tr[y].son[t^1]].cnt;
if(dr-dl)return query(tr[x].son[t^1],tr[y].son[t^1],v,res|(1<<dep),dep-1);
else return query(tr[x].son[t],tr[y].son[t],v,res,dep-1);
}
int main()
{
n=getint();
for(int i=1;i<=n;i++)a[i].val=getint(),a[i].pos=i,Insert(rt[i-1],rt[i],a[i].val,30);
sort(a+1,a+n+1);
S.insert(-1),S.insert(-2),S.insert(INF),S.insert(INF+1),S.insert(a[1].pos);
for(int i=2;i<=n;i++)
{
it1=it2=S.upper_bound(a[i].pos);
int l=(*--(--it1))+1,r=(*++it2)-1;
l=max(1,l),r=min(r,n);
if(l!=r)ans=max(ans,query(rt[l-1],rt[r],a[i].val,0,30));
S.insert(a[i].pos);
}
cout<<ans;
return 0;
}文章浏览阅读196次，点赞2次，收藏2次。解决方案：秒杀整体设计秒杀技术实现核心思想是：运用缓存减少数据库瞬间的访问压力读取商品详细信息：运用缓存，当用户点击抢购时减少缓存中的库存数量，当库存数为0时或活动期结束时，同步到数据库产生的秒杀预订单：也不会立刻写到数据库中，而是先写到缓存，当用户付款成功后再写入数据库1. 秒杀商品压入Redis缓存秒杀由B端存入MYSQL，设置定时任务，每隔一段时间就从MYSQL中将符合条件的数据从MYSQL中查询出来并存入缓存中，redis以Hash类型进行数据存储（namespace=时间，key=商
文章浏览阅读1.6k次。仿QQ即时通讯软件前要说明： 编程环境：Window7/WinXP、Visual C++6.0 软件分客户端、服务器、数据库三块。其中，服务器和数据库整合在单机上了。====================================================客户端登录界面：=======================================================客户端主界面：(最大化与正常窗体)===================_visual studio模仿 qq 完成一套即时通信软件。
文章浏览阅读4.5k次。今天写web项目作业时，发现jsp中“Cannot return from outside a function or method” 提示return出错，百度了一下，网上说这是myeclipse的一个bug,去掉return就好了，去掉之后果然不报错，但是之后发现onSubmit()不能阻止表单提交，再百度之，原来这个return还真不能去掉。以下就是今天错误的解决方法 1_return outside method
文章浏览阅读7.2k次，点赞3次，收藏64次。import requestsfrom bs4 import BeautifulSoupfrom pandas.core.frame import DataFrameimport reimport timeclass Graduate: def __init__(self, province, category): self.head = { ..._考研信息api
文章浏览阅读330次，点赞8次，收藏10次。HTML实例网页代码, 本实例适合于初学HTML的同学。该实例里面有设置了css的样式设置，有div的样式格局，这个实例比较全面，有助于同学的学习,本文将介绍如何通过从头开始设计个人网站并将其转换为代码的过程来实践设计。 精彩专栏推荐 【作者主页——获取更多优质源码】 【学习资料/简历模板/面试资料/ 网站设计与制作】 【web前端期末大作业——毕设项目精品实战案例】---@[TOC](文章目录)一、网页介绍1 网页简介：此作品为学生个人主
文章浏览阅读724次。Meng Qu，Yoshua Bengio，Jian TangMontreal Institute for Learning Algorithms (MILA), Uni..._马尔可夫 图神经网络
文章浏览阅读2.4k次，点赞2次，收藏8次。如果用vs2019的话，这个不是问题，vs会时不时的问源程序在哪里呀，你打开一下呀之类的。但用QtCreator这家伙的话，基本上默认状态下就是不闻不问。首先，我假设你下载了安装程序 ，3D进阶之OSG: 编译osgQt（附：Qt的下载与安装）_高精度计算机视觉的博客-程序员宅基地_osg编译osgQt是个简单的小项目，其实没有必要额外的编译，最核心的是个名为GraphicsWindowQt的类，只需要复制GraphicsWindowQt.h和GraphicsWindowQt.cpp到QT工程里面就_qt debug information file
文章浏览阅读1.8k次。What's promiseAngular’s event system provides a lot of power to our Angular apps. One of the most powerful features that it enables is automatic resolution of promises.Promises are a method of
文章浏览阅读741次。android.util.AndroidRuntimeException: Calling startActivity() from outside of an ActivityCaused by: android.util.AndroidRuntimeException: Calling startActivity() from outside of an Activity contex_android android.util.androidruntimeexception: calling startactivity() from o
文章浏览阅读5.9k次，点赞3次，收藏17次。集群资源调度系统设计架构总结之前为完成《AWS 下 Kylin 调度系统的设计》（https://io-meter.com/2017/10/13/kylin-aws-scheduler-system/），阅读了大量 集群资源管理和任务调度的资料和论文。了解了如Hadoop YARN、Mesos、Spark Drizzle、Borg/Kubernetes 和O mega等系统的调度器_任务调度集群资源怎么写
文章浏览阅读528次。B~树 1.前言：动态查找树主要有：二叉查找树（Binary Search Tree），平衡二叉查找树（Balanced Binary Search Tree），红黑树 (Red-Black Tree )，B-tree/B+-tree/ B*-tree (B~Tree)。前三者是典型的二叉查找树结构，其查找的时间复杂度O(log2N)与树的深度相关，那么
文章浏览阅读527次。你学编程的方法对吗？你是否手写代码？你是否死记硬背？你是否把学文科的方法应用到编程上？你是否前面学后面忘？你是否在抱怨编程难学？如果你遇到上面这些问题，很遗憾的告诉你，你学习的方法错了。这些问题我都遇到过，我一开始学编程的时候，感觉可难了，当时就是照着别人的视频和教程一点点的学，一点点的敲代码，记忆，可是几个月过去了又忘光了，不断重复这种死循环。直到有一天，我认识了一位前辈，我发现，我错了，编程不是这么学的。1.不要看视频学习那编程应该怎么学呢？首先我不建议你去看视频学习，因为这种学_文科生进在华为云工作需要学编程代码