# SPOJ MAXOR （分块 || 可持久化字典树 || 异或）（好题）

2018/01/10 11:31

You are given a sequence A[1], A[2], ..., A[N]. (0 ≤ A[i] < 231, 1 ≤ N ≤ 12000).

A query is defined as follows:

• Query(x,y) = Max { a[i] xor a[i+1] xor ... xor a[j] ; l ≤ i ≤ j ≤ r }.
• l = min ( ((x+lastans) mod N)+1 , ((y+lastans) mod N)+1 ).
• r = max ( ((x+lastans) mod N)+1 , ((y+lastans) mod N)+1 ).
• lastans[1] = 0 , lastans[i] = Query[i-1].

Given M queries, your program must output the results of these queries. (0 ≤ M ≤ 6000).

IMPORTANT : PROBLEM ENHANCED. ( I'M SO SORRY.. )

### Input

• The first line of the input file contains 2 numbers : N M.
• In the second line, N numbers follow.
• M lines follow, where line i contains 2 numbers xi and yi.

### Output

Your program should output the results of the M queries, one query per line.

### Example

Input:
3 3
1 4 3
0 1
0 1
4 3

Output:
5
7
7

### 解法： 分块+可持久化字典树

1. 首先，分块，把每个点分属于一个块，belong[i]=(i-1)/sqrt(n) +1;
2. 预处理得到每个块的左边界到右边的点的区间的最大异或，即如果(i-1)%sqrt(n)=0 ，则计算Maxxor[belong[i],j]，(i<=j<=n)（这里很关键，不过先别管这里这么实现的，看完
3. 对于每个询问[L,R],由于我们预处理得到了[belong[L]+1,R]的最大异或和，现在只要计算[t,R]的最大异或和(L<=t<=belong[L]的右边界)。

-------------------------------------------嗯，看似行得通，怎么实现呢？----------------------------------------

#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=21010;
struct nmphy
{
int n,m,a[maxn],G[125][maxn];
int rt[maxn],sum[maxn*100],ch[maxn*100][2],cnt;
int B,group[maxn],L;

int swap(int &u,int &v)  { u^=v; v^=u; u^=v; }
int Max (int &x,int y)   { if(y>x) x=y;}

void init()
{
scanf("%d%d",&n,&m);
n++;  int tmp=0;
for(int i=2;i<=n;i++){ //这里i==1是为了把a[1]==0加进去。
scanf("%d",&a[i]);
a[i]^=a[i-1];
tmp|=a[i];         //得到最长位。
}
L=0;  while(tmp) L++,tmp>>=1; if(!L) L=1;
for(int i=1;i<=n;i++) insert(rt[i-1],rt[i],a[i],L-1);
}

void insert(int x,int &y,int val,int pos)
{
sum[y=++cnt]=sum[x]+1;
if(pos==0)  return ;
int d=(val>>pos)&1;
ch[y][d^1]=ch[x][d^1];
insert(ch[x][d],ch[y][d],val,pos-1);
}

int query(int x,int y,int val)
{
int res=0;
for(int i=L-1;i>=0;i--){
int d=(val>>i)&1;
if(sum[ch[y][d^1]]-sum[ch[x][d^1]]>0) {
res+=(1<<i);
x=ch[x][d^1];y=ch[y][d^1];
}
else x=ch[x][d],y=ch[y][d];
} return res;
}
int cal(int x, int y, int v, int d) {
if (d < 0) return 0;
int p = v >> d & 1; int tmp = sum[ch[y][p ^ 1]] - sum[ch[x][p ^ 1]];
if (tmp > 0) return (1 << d) + cal(ch[x][p ^ 1], ch[y][p ^ 1], v, d - 1);
else return cal(ch[x][p], ch[y][p], v, d - 1);
}

void divide()
{
while(B*B<n) B++;
for(int i=1;i<=n;i++) {
group[i]=(i-1)/B+1;
if((i-1)%B==0){
for(int j=i;j<=n;j++){
G[group[i]][j]=cal(rt[i],rt[j],a[j],L-1);
Max(G[group[i]][j],G[group[i]][j-1]);
}
}
}
}

void solve()
{
int ans=0,tmp,l,r;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&l,&r);
l=(l+(long long)ans)%(n-1)+1;
r=(r+(long long)ans)%(n-1)+1;
if(l>r) swap(l,r); r++;
ans=G[group[l]+1][r];
for(int j=l;j<=r&&group[j]==group[l];j++){
tmp=cal(rt[l],rt[r],a[j],L-1);
Max(ans,tmp);
}
printf("%d\n",ans);
}
}
}Tree;
int main()
{
Tree.init();    //输入，持久化Trie树
Tree.divide();  //分块，预处理块尾到后面的信息。
Tree.solve();   //快头之后的信息+块头前的暴力。
return 0;
}

0
0 收藏

0 评论
0 收藏
0