爱悠闲 > BZOJ 2741 【FOTILE模拟赛】L 分块+可持久化Trie树

BZOJ 2741 【FOTILE模拟赛】L 分块+可持久化Trie树

分类: BZOJ  |  标签: BZOJ,BZOJ2741,分块,可持久化Trie树  |  作者: popoqqq 相关  |  发布日期 : 2014-10-20  |  热度 : 573°

题目大意:给定一个序列,多次询问[l,r]中最大子序异或和 强制在线

一直RE的同学注意,本题的强制在线如果直接加会爆int导致调用数组下标为负

首先我们有一个转化 维护前缀异或和数组a[] 那么[l,r]中最大子序异或和就是a数组中[l-1,r]中任取两个数的最大异或值

然后分块处理 对于每块的第一个数a[i] 我们依次处理出对于所有的j>=i的[i,j]中的最大异或值 即s[i][j]=max(a[j]与i~j所有数中的最大异或值,s[i][j-1])

然后对于每个询问[l,r],设l后面第一个块的第一个数为x,我们已知[x,r],对于[l,x)部分的每个数在可持久化Trie树上找即可 注意x可能大于r 

从早上RE到现在0.0 各种对拍,解决了各种WA,次次交上去都RE0.0 最后知道真相的我眼泪掉下来

此外本题n=12000 不是小于等于 虽然这没什么用0.0

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define M 13000
#define ls son[0]
#define rs son[1]
using namespace std;
struct Trie{
	Trie *son[2];
	int cnt;
}*trie[M],**tree=trie+1,mempool[M*40],*C=mempool;
int n,m,block,ans,a[M],s[120][M];
inline Trie* New_Node(Trie*_,Trie*__,int ___)
{
	C->son[0]=_;
	C->son[1]=__;
	C->cnt=___;
	return C++;
}
Trie* Build_Tree(Trie *p,int x,int pos)
{
	if(!pos)
		return New_Node(0x0,0x0,p->cnt+1);
	if(~x&pos)
		return New_Node(Build_Tree(p->ls,x,pos>>1),p->rs,p->cnt+1);
	else
		return New_Node(p->ls,Build_Tree(p->rs,x,pos>>1),p->cnt+1);
}
int Get_Ans(Trie *l,Trie *r,int x,int pos)
{
	int num=x&pos?1:0;  
    if(!pos)  
        return 0;  
    if(r->son[!num]->cnt-l->son[!num]->cnt)  
        return pos + Get_Ans(l->son[!num],r->son[!num],x,pos>>1);  
    else  
        return Get_Ans(l->son[num],r->son[num],x,pos>>1);  
}
int main()
{
	
	//freopen("xor.in","r",stdin);
	//freopen("xor.out","w",stdout);
	
	int i,j,x,y;
	cin>>n>>m;
	tree[-1]=New_Node(C,C,0);
	tree[0]=Build_Tree(tree[-1],0,1<<30);
	for(i=1;i<=n;i++)
		scanf("%d",&a[i]),tree[i]=Build_Tree(tree[i-1],a[i]^=a[i-1],1<<30);
	block=static_cast<int>(sqrt(n+1));
	for(i=0;i*block<=n;i++)
		for(j=i*block;j<=n;j++)
			s[i][j]=max(Get_Ans(tree[i*block-1],tree[j],a[j],1<<30),j?s[i][j-1]:0);
	for(i=1;i<=m;i++)
	{
		if(i==16)
			++i,--i;
		scanf("%d%d",&x,&y);
		x=((long long)x+ans)%n+1;y=((long long)y+ans)%n+1;
		if(x>y) swap(x,y); --x;
		int temp=x/block+1;
		ans=s[temp][y];
		for(temp=min(temp*block-1,y);temp>=x;--temp)
			ans=max(Get_Ans(tree[x-1],tree[y],a[temp],1<<30),ans);
		printf("%d\n",ans);
	}
}