BZOJ 2741 L

发表于 | 更新于

Link

Solution

当然首先把XOR前缀和，转换成在[l−1,r][l-1,r]中找两个元素使它们的XOR最大。 这种分块的套路好像都差不多啊。 对于每个块bb的块首元素head[b]head[b]，f[b][i]f[b][i]表示点ii和区间[head[b],i][head[b],i]中元素的XOR最大值，用可持久化Trie。 对于每个询问[l−1,r][l-1,r]，分成两部分[l−1,head[b]−1],[head[b],r][l-1,head[b]-1],[head[b],r]，其中head[b]head[b]是ll后面的第一个块首元素。后半部分已经预处理，前半部分只需要枚举每个数，查找它在区间[l,r][l,r]中的最大XOR值。

Tips

分块思想一种套路。 把int右移32位会爆炸，会出来1!!切记！！

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
//Code by Lucida
#include<bits/stdc++.h>
#define get(x) scanf("%d",&x)
//#define debug(x) std::cout<<#x<<'='<<x<<std::endl
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
const int MAXN=12000+10,MAXB=200;
typedef long long LL;
using std::max;
using std::min;
namespace iTrie
{
	const int LEN=31;//32 各种错误？？？？
	const int SIZE=LEN*MAXN<<1;
	struct Node
	{
		Node *son[2];
		int cnt;
		Node(){son[0]=son[1]=0,cnt=0;}
	}*POOL=(Node*)malloc(SIZE*sizeof(Node)),*ME=POOL,*null=new(ME++)Node,*root[MAXN];
	int rc;
	Node *newNode(){return new(ME++) Node;}
	Node *newNode(Node *old)
	{
		static Node *cur;cur=new(ME++) Node;
		*cur=*old;return cur;
	}
	void Insert(Node *&rt,int x)
	{
		Node *cur=rt=newNode(rt);cur->cnt++;
		for(int i=LEN;~i;i--)
		{
			int c=(x>>i)&1;
			cur=cur->son[c]=newNode(cur->son[c]);
			cur->cnt++;
		}
	}
	bool next(Node *pl,Node *pr,int c){return pr->son[c]->cnt-pl->son[c]->cnt;}
	int Query(Node *pl,Node *pr,int x)
	{
		int res=x;
		for(int i=LEN;~i;i--)
		{
			int c=(x>>i)&1;
			if(next(pl,pr,c^1)) 
				pl=pl->son[c^1],pr=pr->son[c^1],res|=(1<<i);
			else 
				pl=pl->son[c],pr=pr->son[c],res&=~(1<<i);//没把这一位清零
		}
		return res;
	}
	int Query(int l,int r,int x)//maxxorsumofx with num in [l,r]
	{
		return Query(root[l],root[r+1],x);
	}
}using namespace iTrie;
int main()
{
	null->son[0]=null->son[1]=root[0]=null;Insert(root[rc=1]=root[0],0);
	static int a[MAXN],f[MAXB][MAXN],bn[MAXN],bhe[MAXN],xorsum[MAXN];
	int n,m;get(n),get(m);
	int bsz=(int)sqrt(n+1),bc=n/bsz+(bool)(n%bsz);
	for(int i=1;i<=n;i++)
	{
		get(a[i]);xorsum[i]=xorsum[i-1]^a[i];
		++rc;Insert(root[rc]=root[rc-1],xorsum[i]);
		bn[i]=(i-1)/bsz+1;
		if(bn[i]!=bn[i-1]) bhe[bn[i]]=i;
	}
	for(int b=bc;b;b--)
		for(int i=bhe[b];i<=n;i++)
			f[b][i]=max(f[b][i-1],Query(bhe[b]-1,i,xorsum[i]));
	int last=0;
	for(int i=1;i<=m;i++)
	{
		int l,r,x,y;get(x),get(y);
		l=min(((LL)x+last)%n+1,((LL)y+last)%n+1);
		r=max(((LL)x+last)%n+1,((LL)y+last)%n+1);
		if(bn[l]==bn[r])
		{
			last=0;
			for(int p=l;p<=r;p++) chkmx(last,Query(l-1,r,xorsum[p]));
		}
		else
		{
			last=f[bn[l]+1][r];
			for(int p=l-1;p<bhe[bn[l]+1];p++)	chkmx(last,Query(l-1,r,xorsum[p]));
		}
		printf("%d\n",last);
	}
	return 0;
}
/* AC Record(Bugs) *
 * RE sizeof array to small
 * WA
 * * * * * * * * * */