BZOJ3166 [HEOI2013]ALO

题面

Welcome to ALO ( Arithmetic and Logistic Online)。这是一个 VR MMORPG, 如名字所见,到处充满了数学的谜题

现在你拥有 n 颗宝石,每颗宝石有一个能量密度,记为 ai,这些宝石的能量 密度两两不同。现在你可以选取连续的一些宝石(必须多于一个)进行融合,设 为 ai, ai+1, …, aj,则融合而成的宝石的能量密度为这些宝石中能量密度的次大值 与其他任意一颗宝石的能量密度按位异或的值,即,设该段宝石能量密度次大值 为 k,则生成的宝石的能量密度为 max{k xor ap | ap ≠ k , i ≤ p ≤ j}

现在你需要知道你怎么选取需要融合的宝石,才能使生成的宝石能量密度最大

思路

如果知道次大值和区间的话,那蒟蒻桑一定可以做到的吧,呐呐呐。

首先这道题看着很不可做,因为如果爆枚区间并用主席树搞次大值的话那就是$N^2logN$了,显然不可过。让我们来思考一下,首先可持久化$trie$的$log$肯定不能省下,那我们考虑优化这个查找次大值的过程。我们反向思考,不要找区间的次大值,而是找次大值对应的区间。对于每一个点。它作为次大值对应的区间如图所示。

绿色的为该点,红色的为比该点大的值,L是向左第一个比该点大的数,LL是向左第二个比该点大的数,R是向右第一个比该点大的数,RR是向右第二个比该点大的数,蓝色即为该点作为次大值对应的最大的可行区间。

但是有特殊情况,比如向左找不到$L$或者找不到$LL$,向右找不到$R$或者找不到$RR$。

需要自己开动脑筋大力分类讨论,至于怎么找$L$,$LL$,$R$,$RR$的位置🐎,线段树set或者链表并查集什么都可以⑧

代码

#include<bits/stdc++.h>
using namespace std;

inline void read(int &x)
{
    int f=1;x=0;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
    x*=f;
}
int n,cnt=1,rt[100005],Max=0;
struct trie{int ls,rs,size;}t[100005*32];
struct seg{int L,R;}tree[4*100005];
struct node{int num,wz;}a[100005];
bool cmp1(node x,node y){return x.num>y.num;}
inline void update(int root)
{
    if (tree[root<<1].L==0) tree[root].L=tree[root<<1|1].L;
    if (tree[root<<1|1].L==0) tree[root].L=tree[root<<1].L;
    if (tree[root<<1].L!=0&&tree[root<<1|1].L!=0) tree[root].L=tree[root<<1|1].L;
    if (tree[root<<1].R==0) tree[root].R=tree[root<<1|1].R;
    if (tree[root<<1|1].R==0) tree[root].R=tree[root<<1].R;
    if (tree[root<<1].R!=0&&tree[root<<1|1].R!=0) tree[root].R=tree[root<<1].R;
}
inline void add(int root,int l,int r,int x)
{
    if (l==r) {tree[root].L=x;tree[root].R=x;return;}
    int mid=l+r>>1;
    if (x<=mid) add(root<<1,l,mid,x);
    else add(root<<1|1,mid+1,r,x);
    update(root);
}
inline int ask_L(int root,int l,int r,int ql,int qr)
{
	if (ql>qr) return 0;
    if (l==ql&&r==qr) return tree[root].L;
    int mid=l+r>>1;
    if (qr<=mid) return ask_L(root<<1,l,mid,ql,qr);
    if (ql>mid) return ask_L(root<<1|1,mid+1,r,ql,qr);
    if (ql<=mid&&qr>mid) return (ask_L(root<<1|1,mid+1,r,mid+1,qr)!=0?ask_L(root<<1|1,mid+1,r,mid+1,qr):ask_L(root<<1,l,mid,ql,mid)); 
}
inline int ask_R(int root,int l,int r,int ql,int qr)
{
	if (ql>qr) return 0;
    if (l==ql&&r==qr) return tree[root].R;
    int mid=l+r>>1;
    if (qr<=mid) return ask_R(root<<1,l,mid,ql,qr);
    if (ql>mid) return ask_R(root<<1|1,mid+1,r,ql,qr);
    if (ql<=mid&&qr>mid) return (ask_R(root<<1,l,mid,ql,mid)!=0?ask_R(root<<1,l,mid,ql,mid):ask_R(root<<1|1,mid+1,r,mid+1,qr)); 
}
inline void insert(int pre,int &root,int i,int x)
{
    root=++cnt;
    t[root]=t[pre];
    t[root].size++;
	if (i<0) return;
    if ((x>>i)&1) insert(t[pre].rs,t[root].rs,i-1,x);
    else insert(t[pre].ls,t[root].ls,i-1,x);
}
inline int query(int pre,int root,int i,int x)
{
    if (i<0) return 0;
    if ((x>>i)&1)
    {
    	if (t[t[root].ls].size-t[t[pre].ls].size>0) return query(t[pre].ls,t[root].ls,i-1,x)+(1<<i);
    	else return query(t[pre].rs,t[root].rs,i-1,x);
	}
    else
    {
    	if (t[t[root].rs].size-t[t[pre].rs].size>0) return query(t[pre].rs,t[root].rs,i-1,x)+(1<<i);
    	else return query(t[pre].ls,t[root].ls,i-1,x);
    }
}
int main()
{
    read(n);
    for (int i=1;i<=n;i++) read(a[i].num),a[i].wz=i,insert(rt[i-1],rt[i],30,a[i].num);
    sort(a+1,a+n+1,cmp1);
    for (int i=1;i<=n;i++) 
    {
		add(1,1,n,a[i].wz);
        if (i==1) continue;
        if (i==2){Max=max(Max,query(rt[0],rt[n],30,a[i].num));continue;}
        int L=ask_L(1,1,n,1,a[i].wz-1),R=ask_R(1,1,n,a[i].wz+1,n);
        int LL=ask_L(1,1,n,1,L-1),RR=ask_R(1,1,n,R+1,n);
        if (LL==0&&L!=0) Max=max(Max,query(rt[0],rt[R-1],30,a[i].num));
        if (RR==0&&R!=0) Max=max(Max,query(rt[L],rt[n],30,a[i].num));
        if (L==0) Max=max(Max,query(rt[0],rt[RR-1],30,a[i].num));
        if (R==0) Max=max(Max,query(rt[LL],rt[n],30,a[i].num));
        if (LL!=0&&R!=0) Max=max(Max,query(rt[LL],rt[R-1],30,a[i].num));
        if (L!=0&&RR!=0)Max=max(Max,query(rt[L],rt[RR-1],30,a[i].num));
    }
    cout<<Max<<endl;
	return 0;
} 
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇