首页 > 代码库 > BZOJ2741: 【FOTILE模拟赛】L

BZOJ2741: 【FOTILE模拟赛】L

2741: 【FOTILE模拟赛】L

Time Limit: 15 Sec  Memory Limit: 162 MB
Submit: 1170  Solved: 303
[Submit][Status]

Description

FOTILE得到了一个长为N的序列A,为了拯救地球,他希望知道某些区间内的最大的连续XOR和。
即对于一个询问,你需要求出max(Ai xor Ai+1 xor Ai+2 ... xor Aj),其中l<=i<=j<=r。
为了体现在线操作,对于一个询问(x,y):
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是上次询问的答案,一开始为0。

Input

第一行两个整数N和M。
第二行有N个正整数,其中第i个数为Ai,有多余空格。
后M行每行两个数x,y表示一对询问。

Output

 

共M行,第i行一个正整数表示第i个询问的结果。

Sample Input

3 3
1 4 3
0 1
0 1
4 3


Sample Output

5
7
7

HINT



HINT

N=12000,M=6000,x,y,Ai在signed longint范围内。

Source

By seter

题解:
搬运题解:by seter

分成长度为L的块,每块的第一个点叫做关键点,则总共有K=N/L个关键点。

处理出一个K*N的数组,表示每个关键点到之后每个点的答案。这个对于一个关键点是可以O(NlgN)弄出来的,用一般的trie就可以了,这个不会的话可以先去水水USACO再来。

然后对于一个询问(u,v),可以分解成(u,v)和(X,v),其中X是u之后的第一个关键点。

那么(X,v)已经处理出来了,剩下的就是u...X这O(L)个数在(u,v)中的max xor了。

问题转化为,求一段内与X的异或最大值。

这个东西用ChairTrie是可以随便减出来的。ChairTrie和ChairTree差不多,就是函数式Trie,从高到低处理X的某一位,如果可以往相反方向走,就走,就可以了。。。

一些注释写在代码里
代码:
  1 #include<cstdio>  2   3 #include<cstdlib>  4   5 #include<cmath>  6   7 #include<cstring>  8   9 #include<algorithm> 10  11 #include<iostream> 12  13 #include<vector> 14  15 #include<map> 16  17 #include<set> 18  19 #include<queue> 20  21 #include<string> 22  23 #define inf 1000000000 24  25 #define maxn 150000+5 26  27 #define maxm 5000000+5 28 #define maxk 150 29  30 #define eps 1e-10 31  32 #define ll long long 33  34 #define pa pair<int,int> 35  36 #define for0(i,n) for(int i=0;i<=(n);i++) 37  38 #define for1(i,n) for(int i=1;i<=(n);i++) 39  40 #define for2(i,x,y) for(int i=(x);i<=(y);i++) 41  42 #define for3(i,x,y) for(int i=(x);i>=(y);i--) 43  44 #define mod 1000000007 45  46 using namespace std; 47  48 inline int read() 49  50 { 51  52     int x=0,f=1;char ch=getchar(); 53  54     while(ch<0||ch>9){if(ch==-)f=-1;ch=getchar();} 55  56     while(ch>=0&&ch<=9){x=10*x+ch-0;ch=getchar();} 57  58     return x*f; 59  60 } 61 int n,m,q,tot,rt[maxn],id[maxm],t[maxm][2],a[maxn],b[maxk][maxn]; 62 inline void insert(int pre,int x,int k) 63 { 64     int now=rt[k]=++tot;id[tot]=k; 65     for3(i,30,0) 66     { 67         int j=(x>>i)&1; 68         t[now][j^1]=t[pre][j^1];//空指针指向原来的 69         t[now][j]=++tot;id[tot]=k; 70         now=tot; 71         pre=t[pre][j]; 72     } 73 } 74 inline int ask(int l,int r,int x) 75 { 76     int ans=0,now=rt[r]; 77     for3(i,30,0) 78     { 79         int j=((x>>i)&1)^1; 80         if(id[t[now][j]]>=l)ans|=1<<i;else j^=1;//下面的节点的id都小于l,所以要改变方向 81         now=t[now][j]; 82     } 83     return ans; 84 } 85  86 int main() 87  88 { 89  90     freopen("input.txt","r",stdin); 91  92     freopen("output.txt","w",stdout); 93  94     n=read();q=read(); 95     for1(i,n)a[i]=a[i-1]^read(); 96     id[0]=-1; 97     insert(rt[0],a[0],0);//插入0 98     for1(i,n)insert(rt[i-1],a[i],i);//挨个插入前缀异或值 99     int len=sqrt(n);m=n/len+(n%len!=0);100     for0(i,m-1)101      for2(j,i*len+1,n)102       b[i][j]=max(b[i][j-1],ask(i*len,j-1,a[j]));//分块,用a[j]去查询在i*len-j-1的最大值103     int ans=0;104     while(q--)105     {106         int x=((ll)read()+(ll)ans)%n+1,y=((ll)read()+(ll)ans)%n+1;107         if(x>y)swap(x,y);x--;108         int bx=x/len+(x%len!=0);109         ans=bx*len<y?b[bx][y]:0;//大块的答案已经得到110         for2(j,x,min(bx*len,y))111          ans=max(ans,ask(x,y,a[j]));//用小块内的点暴力查询max112         printf("%d\n",ans);113     }114 115     return 0;116 117 }  
View Code

 

BZOJ2741: 【FOTILE模拟赛】L