正文
【BZOJ3166】[Heoi2013]Alo 可持久化Trie树+set
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
【BZOJ3166】[Heoi2013]Alo
Description
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}。
现在你需要知道你怎么选取需要融合的宝石，才能使生成的宝石能量密度最大。
Input
第一行，一个整数 n，表示宝石个数。
第二行， n个整数，分别表示a1至an，表示每颗宝石的能量密度，保证对于i ≠ j有 ai ≠ aj。
Output
输出一行一个整数，表示最大能生成的宝石能量密度。
Sample Input
5
9 2 1 4 7
Sample Output
14
HINT
【样例解释】
选择区间[1,5]，最大值为 7 xor 9。
对于 100%的数据有 1 ≤ n ≤ 50000, 0 ≤ ai ≤ 10^9
题解
：如果我们知道了对于一个数i，它是那些区间的次大值，然后直接用可持久化Trie树+贪心就OK了，现在问题是i到底是那些区间的次大值。
一个不难想的思路就是将所有数排序，然后一个一个扔到原数组里（我一开始从小到大排的序，结果发现没法做）
所以我们将所有数从大到小排序，然后一个一个扔回到数组里，这是他的前驱和后继都是刚好比它大的数，那么它(前驱的前驱，后继的后继)这段区间里的所有包含它的子区间的次大值一定就是这个数。具体实现方法：用set维护一下每个数的位置就好了
别忘了用set之前，先无脑的把0和n+1都扔到set里去
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;
const int maxn=50010;
int n,tot,ans;
int ch[maxn*100][2],s[maxn*100],v[maxn],ls[maxn],rs[maxn],rt[maxn];
set<int> ms;
struct node
{
int val,org;
}p[maxn];
int rd()
{
int ret=0,f=1; char gc=getchar();
while(gc<'0'||gc>'9') {if(gc=='-')f=-f; gc=getchar();}
while(gc>='0'&&gc<='9') ret=ret*10+gc-'0',gc=getchar();
return ret*f;
}
void ins(int x,int &y,int num)
{
y=++tot;
int i,u=y,a;
for(i=1<<30;i;i>>=1)
{
a=(num&i)>0;
ch[u][a]=++tot,ch[u][a^1]=ch[x][a^1],u=ch[u][a],x=ch[x][a],s[u]=s[x]+1;
}
}
int query(int a,int b,int num)
{
int i,sum=0,d;
for(i=1<<30;i;i>>=1)
{
d=!(num&i);
if(s[ch[b][d]]-s[ch[a][d]]) a=ch[a][d],b=ch[b][d],sum|=i;
else a=ch[a][d^1],b=ch[b][d^1];
}
return sum;
}
bool cmp(node a,node b)
{
return a.val>b.val;
}
int main()
{
n=rd();
int i,j;
ins(0,rt[0],0);
for(i=1;i<=n;i++) v[i]=rd(),p[i].val=v[i],p[i].org=i,ins(rt[i-1],rt[i],v[i]);
sort(p+1,p+n+1,cmp);
set<int>::iterator it;
ms.insert(0),ms.insert(n+1);
for(i=1;i<=n;i++)
{
if(i>1)
{
it=ms.upper_bound(p[i].org),it++;
if(it==ms.end()) rs[p[i].org]=n;
else rs[p[i].org]=(*it)-1;
it--,it--;
if(it==ms.begin()) ls[p[i].org]=0;
else it--,ls[p[i].org]=(*it);
}
ms.insert(p[i].org);
}
for(i=1;i<=n;i++)
{
if(i==p[1].org) continue;
ans=max(ans,query(rt[ls[i]],rt[rs[i]],v[i]));
}
printf("%d",ans);
return 0;
}
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}。
现在你需要知道你怎么选取需要融合的宝石，才能使生成的宝石能量密度最大。
Input
第一行，一个整数 n，表示宝石个数。
第二行， n个整数，分别表示a1至an，表示每颗宝石的能量密度，保证对于i ≠ j有 ai ≠ aj。
Output
输出一行一个整数，表示最大能生成的宝石能量密度。
Sample Input
5
9 2 1 4 7
Sample Output
14
HINT
【样例解释】
选择区间[1,5]，最大值为 7 xor 9。
对于 100%的数据有 1 ≤ n ≤ 50000, 0 ≤ ai ≤ 10^9
题解
：如果我们知道了对于一个数i，它是那些区间的次大值，然后直接用可持久化Trie树+贪心就OK了，现在问题是i到底是那些区间的次大值。
一个不难想的思路就是将所有数排序，然后一个一个扔到原数组里（我一开始从小到大排的序，结果发现没法做）
所以我们将所有数从大到小排序，然后一个一个扔回到数组里，这是他的前驱和后继都是刚好比它大的数，那么它(前驱的前驱，后继的后继)这段区间里的所有包含它的子区间的次大值一定就是这个数。具体实现方法：用set维护一下每个数的位置就好了
别忘了用set之前，先无脑的把0和n+1都扔到set里去
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;
const int maxn=50010;
int n,tot,ans;
int ch[maxn*100][2],s[maxn*100],v[maxn],ls[maxn],rs[maxn],rt[maxn];
set<int> ms;
struct node
{
int val,org;
}p[maxn];
int rd()
{
int ret=0,f=1; char gc=getchar();
while(gc<'0'||gc>'9') {if(gc=='-')f=-f; gc=getchar();}
while(gc>='0'&&gc<='9') ret=ret*10+gc-'0',gc=getchar();
return ret*f;
}
void ins(int x,int &y,int num)
{
y=++tot;
int i,u=y,a;
for(i=1<<30;i;i>>=1)
{
a=(num&i)>0;
ch[u][a]=++tot,ch[u][a^1]=ch[x][a^1],u=ch[u][a],x=ch[x][a],s[u]=s[x]+1;
}
}
int query(int a,int b,int num)
{
int i,sum=0,d;
for(i=1<<30;i;i>>=1)
{
d=!(num&i);
if(s[ch[b][d]]-s[ch[a][d]]) a=ch[a][d],b=ch[b][d],sum|=i;
else a=ch[a][d^1],b=ch[b][d^1];
}
return sum;
}
bool cmp(node a,node b)
{
return a.val>b.val;
}
int main()
{
n=rd();
int i,j;
ins(0,rt[0],0);
for(i=1;i<=n;i++) v[i]=rd(),p[i].val=v[i],p[i].org=i,ins(rt[i-1],rt[i],v[i]);
sort(p+1,p+n+1,cmp);
set<int>::iterator it;
ms.insert(0),ms.insert(n+1);
for(i=1;i<=n;i++)
{
if(i>1)
{
it=ms.upper_bound(p[i].org),it++;
if(it==ms.end()) rs[p[i].org]=n;
else rs[p[i].org]=(*it)-1;
it--,it--;
if(it==ms.begin()) ls[p[i].org]=0;
else it--,ls[p[i].org]=(*it);
}
ms.insert(p[i].org);
}
for(i=1;i<=n;i++)
{
if(i==p[1].org) continue;
ans=max(ans,query(rt[ls[i]],rt[rs[i]],v[i]));
}
printf("%d",ans);
return 0;
}
第一行，一个整数 n，表示宝石个数。
第二行， n个整数，分别表示a1至an，表示每颗宝石的能量密度，保证对于i ≠ j有 ai ≠ aj。
输出一行一个整数，表示最大能生成的宝石能量密度。
Sample Input
5
9 2 1 4 7
Sample Output
14
HINT
【样例解释】
选择区间[1,5]，最大值为 7 xor 9。
对于 100%的数据有 1 ≤ n ≤ 50000, 0 ≤ ai ≤ 10^9
题解
：如果我们知道了对于一个数i，它是那些区间的次大值，然后直接用可持久化Trie树+贪心就OK了，现在问题是i到底是那些区间的次大值。
一个不难想的思路就是将所有数排序，然后一个一个扔到原数组里（我一开始从小到大排的序，结果发现没法做）
所以我们将所有数从大到小排序，然后一个一个扔回到数组里，这是他的前驱和后继都是刚好比它大的数，那么它(前驱的前驱，后继的后继)这段区间里的所有包含它的子区间的次大值一定就是这个数。具体实现方法：用set维护一下每个数的位置就好了
别忘了用set之前，先无脑的把0和n+1都扔到set里去
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;
const int maxn=50010;
int n,tot,ans;
int ch[maxn*100][2],s[maxn*100],v[maxn],ls[maxn],rs[maxn],rt[maxn];
set<int> ms;
struct node
{
int val,org;
}p[maxn];
int rd()
{
int ret=0,f=1; char gc=getchar();
while(gc<'0'||gc>'9') {if(gc=='-')f=-f; gc=getchar();}
while(gc>='0'&&gc<='9') ret=ret*10+gc-'0',gc=getchar();
return ret*f;
}
void ins(int x,int &y,int num)
{
y=++tot;
int i,u=y,a;
for(i=1<<30;i;i>>=1)
{
a=(num&i)>0;
ch[u][a]=++tot,ch[u][a^1]=ch[x][a^1],u=ch[u][a],x=ch[x][a],s[u]=s[x]+1;
}
}
int query(int a,int b,int num)
{
int i,sum=0,d;
for(i=1<<30;i;i>>=1)
{
d=!(num&i);
if(s[ch[b][d]]-s[ch[a][d]]) a=ch[a][d],b=ch[b][d],sum|=i;
else a=ch[a][d^1],b=ch[b][d^1];
}
return sum;
}
bool cmp(node a,node b)
{
return a.val>b.val;
}
int main()
{
n=rd();
int i,j;
ins(0,rt[0],0);
for(i=1;i<=n;i++) v[i]=rd(),p[i].val=v[i],p[i].org=i,ins(rt[i-1],rt[i],v[i]);
sort(p+1,p+n+1,cmp);
set<int>::iterator it;
ms.insert(0),ms.insert(n+1);
for(i=1;i<=n;i++)
{
if(i>1)
{
it=ms.upper_bound(p[i].org),it++;
if(it==ms.end()) rs[p[i].org]=n;
else rs[p[i].org]=(*it)-1;
it--,it--;
if(it==ms.begin()) ls[p[i].org]=0;
else it--,ls[p[i].org]=(*it);
}
ms.insert(p[i].org);
}
for(i=1;i<=n;i++)
{
if(i==p[1].org) continue;
ans=max(ans,query(rt[ls[i]],rt[rs[i]],v[i]));
}
printf("%d",ans);
return 0;
}
9 2 1 4 7
14
HINT
【样例解释】
选择区间[1,5]，最大值为 7 xor 9。
对于 100%的数据有 1 ≤ n ≤ 50000, 0 ≤ ai ≤ 10^9
题解
：如果我们知道了对于一个数i，它是那些区间的次大值，然后直接用可持久化Trie树+贪心就OK了，现在问题是i到底是那些区间的次大值。
一个不难想的思路就是将所有数排序，然后一个一个扔到原数组里（我一开始从小到大排的序，结果发现没法做）
所以我们将所有数从大到小排序，然后一个一个扔回到数组里，这是他的前驱和后继都是刚好比它大的数，那么它(前驱的前驱，后继的后继)这段区间里的所有包含它的子区间的次大值一定就是这个数。具体实现方法：用set维护一下每个数的位置就好了
别忘了用set之前，先无脑的把0和n+1都扔到set里去
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;
const int maxn=50010;
int n,tot,ans;
int ch[maxn*100][2],s[maxn*100],v[maxn],ls[maxn],rs[maxn],rt[maxn];
set<int> ms;
struct node
{
int val,org;
}p[maxn];
int rd()
{
int ret=0,f=1; char gc=getchar();
while(gc<'0'||gc>'9') {if(gc=='-')f=-f; gc=getchar();}
while(gc>='0'&&gc<='9') ret=ret*10+gc-'0',gc=getchar();
return ret*f;
}
void ins(int x,int &y,int num)
{
y=++tot;
int i,u=y,a;
for(i=1<<30;i;i>>=1)
{
a=(num&i)>0;
ch[u][a]=++tot,ch[u][a^1]=ch[x][a^1],u=ch[u][a],x=ch[x][a],s[u]=s[x]+1;
}
}
int query(int a,int b,int num)
{
int i,sum=0,d;
for(i=1<<30;i;i>>=1)
{
d=!(num&i);
if(s[ch[b][d]]-s[ch[a][d]]) a=ch[a][d],b=ch[b][d],sum|=i;
else a=ch[a][d^1],b=ch[b][d^1];
}
return sum;
}
bool cmp(node a,node b)
{
return a.val>b.val;
}
int main()
{
n=rd();
int i,j;
ins(0,rt[0],0);
for(i=1;i<=n;i++) v[i]=rd(),p[i].val=v[i],p[i].org=i,ins(rt[i-1],rt[i],v[i]);
sort(p+1,p+n+1,cmp);
set<int>::iterator it;
ms.insert(0),ms.insert(n+1);
for(i=1;i<=n;i++)
{
if(i>1)
{
it=ms.upper_bound(p[i].org),it++;
if(it==ms.end()) rs[p[i].org]=n;
else rs[p[i].org]=(*it)-1;
it--,it--;
if(it==ms.begin()) ls[p[i].org]=0;
else it--,ls[p[i].org]=(*it);
}
ms.insert(p[i].org);
}
for(i=1;i<=n;i++)
{
if(i==p[1].org) continue;
ans=max(ans,query(rt[ls[i]],rt[rs[i]],v[i]));
}
printf("%d",ans);
return 0;
}
【样例解释】
选择区间[1,5]，最大值为 7 xor 9。
对于 100%的数据有 1 ≤ n ≤ 50000, 0 ≤ ai ≤ 10^9
题解 ：如果我们知道了对于一个数i，它是那些区间的次大值，然后直接用可持久化Trie树+贪心就OK了，现在问题是i到底是那些区间的次大值。
一个不难想的思路就是将所有数排序，然后一个一个扔到原数组里（我一开始从小到大排的序，结果发现没法做）
所以我们将所有数从大到小排序，然后一个一个扔回到数组里，这是他的前驱和后继都是刚好比它大的数，那么它(前驱的前驱，后继的后继)这段区间里的所有包含它的子区间的次大值一定就是这个数。具体实现方法：用set维护一下每个数的位置就好了
别忘了用set之前，先无脑的把0和n+1都扔到set里去
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;
const int maxn=50010;
int n,tot,ans;
int ch[maxn*100][2],s[maxn*100],v[maxn],ls[maxn],rs[maxn],rt[maxn];
set<int> ms;
struct node
{
int val,org;
}p[maxn];
int rd()
{
int ret=0,f=1; char gc=getchar();
while(gc<'0'||gc>'9') {if(gc=='-')f=-f; gc=getchar();}
while(gc>='0'&&gc<='9') ret=ret*10+gc-'0',gc=getchar();
return ret*f;
}
void ins(int x,int &y,int num)
{
y=++tot;
int i,u=y,a;
for(i=1<<30;i;i>>=1)
{
a=(num&i)>0;
ch[u][a]=++tot,ch[u][a^1]=ch[x][a^1],u=ch[u][a],x=ch[x][a],s[u]=s[x]+1;
}
}
int query(int a,int b,int num)
{
int i,sum=0,d;
for(i=1<<30;i;i>>=1)
{
d=!(num&i);
if(s[ch[b][d]]-s[ch[a][d]]) a=ch[a][d],b=ch[b][d],sum|=i;
else a=ch[a][d^1],b=ch[b][d^1];
}
return sum;
}
bool cmp(node a,node b)
{
return a.val>b.val;
}
int main()
{
n=rd();
int i,j;
ins(0,rt[0],0);
for(i=1;i<=n;i++) v[i]=rd(),p[i].val=v[i],p[i].org=i,ins(rt[i-1],rt[i],v[i]);
sort(p+1,p+n+1,cmp);
set<int>::iterator it;
ms.insert(0),ms.insert(n+1);
for(i=1;i<=n;i++)
{
if(i>1)
{
it=ms.upper_bound(p[i].org),it++;
if(it==ms.end()) rs[p[i].org]=n;
else rs[p[i].org]=(*it)-1;
it--,it--;
if(it==ms.begin()) ls[p[i].org]=0;
else it--,ls[p[i].org]=(*it);
}
ms.insert(p[i].org);
}
for(i=1;i<=n;i++)
{
if(i==p[1].org) continue;
ans=max(ans,query(rt[ls[i]],rt[rs[i]],v[i]));
}
printf("%d",ans);
return 0;
}
