首页 > 代码库 > BZOJ2741[FOTILE模拟赛]L
BZOJ2741[FOTILE模拟赛]L
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
1 4 3
0 1
0 1
4 3
Sample Output
5
7
7
7
7
HINT
N=12000,M=6000,x,y,Ai在signed longint范围内。
题解:
把元素数组aa替换为前缀异或和数组qz,则询问变成了指定区间内最大的两个元素异或和。
假如某个元素x已经确定,那么我们只要在区间中找到一个数y,使x xor y最大。
这可以用字典树在O(log)的复杂度内实现。因为是指定的一个区间,所以要采用可持久化字典树。
为了减少复杂度,采取分块的做法。
将n分为√n块,对于每块的第一个元素i,用a[i,j]表示i到j的区间中的最大连续异或和。
转移方式:a[i,j]:=max(a[i,j-1],qz[j]在[i,j-1]的字典树中的最大异或和)。
注意不要忘了以[i,j]异或和作为答案的情况(即qz[i-1]xor qz[j])。
预处理好a数组后,开始处理询问[l,r]。
找到第一个比l大的分块首元素i(i=k*√n+1),分情况讨论。
若r≥i,则答案为max(a[i,r],qz[l≤j≤i-1]在[j+1,r]的字典树中的最大异或和);
若r<i,则答案为max(qz[l≤j≤r]在[l,j-1]的字典树中的最大异或和),注意考虑以[l,j]异或和作为答案的情况(即qz[l-1]xor qz[j])。
代码:
uses math; var t:array[0..600000,0..1,0..1]of longint; a:array[0..120,0..12001]of longint; qz,aa:array[0..12001]of longint; r:array[0..12001]of longint; b:array[0..34]of longint; i,ii,j,k,n,m,block,mm,cnt,x,y,ans:longint; l,ll,rr:int64; procedure cl(y,yy,z:longint); var i:longint; begin if z=-1 then exit; i:=x and(1 shl z); if i>0 then begin inc(cnt); t[yy,0]:=t[y,0]; t[yy,1,1]:=cnt; t[yy,1,0]:=t[y,1,0]+1; cl(t[y,1,1],t[yy,1,1],z-1); exit; end; inc(cnt); t[yy,1]:=t[y,1]; t[yy,i,1]:=cnt; t[yy,i,0]:=t[y,i,0]+1; cl(t[y,i,1],t[yy,i,1],z-1); end; function qq(y,yy,z:longint):longint; var i:longint; begin if z=-1 then exit(0); i:=x and(1 shl z); if i>0 then begin if t[yy,0,0]-t[y,0,0]>0 then exit(b[z]+qq(t[y,0,1],t[yy,0,1],z-1)); exit(qq(t[y,1,1],t[yy,1,1],z-1)); end; if t[yy,1,0]-t[y,1,0]>0 then exit(b[z]+qq(t[y,1,1],t[yy,1,1],z-1)); exit(qq(t[y,0,1],t[yy,0,1],z-1)); end; begin b[0]:=1; for i:=1 to 30 do b[i]:=b[i-1]*2; readln(n,m); for i:=1 to n do begin read(aa[i]); qz[i]:=aa[i] xor qz[i-1]; x:=qz[i]; inc(cnt); r[i]:=cnt; cl(r[i-1],cnt,30); end; block:=trunc(sqrt(n)*1.5)+1; block:=min(n,block); i:=1; while i<=n do begin inc(mm); a[mm,i]:=aa[i]; for j:=i+1 to n do begin x:=qz[j]; a[mm,j]:=max(a[mm,j-1],x xor qz[i-1]); a[mm,j]:=max(a[mm,j],qq(r[i-1],r[j-1],30)); end; i:=i+block; end; for i:=1 to m do begin readln(ll,rr); l:=max((ll+ans)mod n+1,(rr+ans)mod n+1); ll:=min((ll+ans)mod n+1,(rr+ans)mod n+1); k:=l; j:=ll; l:=0; while block*l+1<=j do inc(l); if block*l+1<=k then begin ans:=a[l+1,k]; l:=block*l; for ii:=j to l do begin x:=qz[ii-1]; ans:=max(ans,qq(r[ii-1],r[k],30)); end; end else begin ans:=aa[j]; for ii:=j+1 to k do begin x:=qz[ii]; ans:=max(ans,x xor qz[j-1]); ans:=max(ans,qq(r[j-1],r[ii-1],30)); end; end; writeln(ans); end; end.
BZOJ2741[FOTILE模拟赛]L
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。