SnackDown 2017 Online Elimination Round Prefix XOR

题目传送门

题意

给出$n$个数,定义上升为$a_i\leq a_i \quad xor \quad a_{i+1} \leq a_i \quad xor \quad a_{i+1} \quad xor \quad a_{i+2} \leq \dots \leq a_i \quad xor \quad a_{i+1} \quad xor \quad \dots \quad xor \quad a_{j}$,问每个区间的上升数对有多少?

思路

设$rig_i$表示以$i$为区间左端,使$(i,j)$满足上升的最大$j$。 设$sum_i$表示$xor$前缀和。 如果$a_r \quad xor \quad a_{r-1} \quad xor \quad \dots \quad xor \quad a_{i-1}>
a_{r+1} \quad xor \quad a_{r} \quad xor \quad \dots \quad xor \quad a_{i-1} $则不满足条件,那么$rig_i\leq r$。 即: 如果$sum_r \quad xor \quad sum_{i-1}> sum_{r+1} \quad xor \quad sum_{i-1} $则不满足条件,那么$rig_i\leq r$。 由于$xor$是位运算,所以考虑二进制下优化。 要满足条件,必须使$sum_r$与$sum_{r+1}$中至少有一位在二进制下不相同。 假设不相同的最高位是第$k$位,那么$sum_{i−1}$的第$k$位其实就有了限制,易得: (二进制下)

  1. $sum_r$的第$k$位为0,那么$sum_{i-1}$的第$k$位必须是1。
  2. $sum_r$的第$k$位为1,那么$sum_{i-1}$的第$k$位必须是0。

那么我们可以倒序枚举$i$,记录$S[j][0/1]$表示当前第$j$位限制为$0/1$时的位置,那样就可以快速求出$rig_i$了。 如果$[l,r]$不存在$rig_i>r$,那么答案显然就是$rig_i-i+1(l \leq i \leq r $且$ rig_i \leq r)$,但如果存在$rig_i>r$,由于不能越界,该部分的答案应该就是$r-i+1(l \leq i \leq r $且$ rig_i > r)$。由于强制在线,用主席树就可以解决了。

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
#include<bits/stdc++.h>
#define int long long
#define MAXN 600010
using namespace std;
int n,m,q,Qt;
int a[MAXN],b[MAXN],rt[MAXN],xo[MAXN],rig[MAXN],S[31][500],Q,ans,ntt;
inline int read(){
int res=0,f=1;char ch=getchar();
while(ch<'0'ch>'9'){if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') res=res*10+ch-'0',ch=getchar();
return res*f;
}
inline void write(int x){
if(x<0) putchar('-'),x=-x;
if(x<10) putchar(x+'0');
else{
write(x/10);
putchar(x%10+'0');
}
}
struct node{
int l,r,sum,cnt;
}tree[MAXN*20];
void insert(int &x,int y,int l,int r,int p){
x=++ntt;
tree[x]=tree[y];
if(l==r){
tree[x].sum+=p;
tree[x].cnt++;
return ;
}
int mid=(l+r)>>1;
if(p<=mid) insert(tree[x].l,tree[y].l,l,mid,p);
else insert(tree[x].r,tree[y].r,mid+1,r,p);
tree[x].sum=tree[tree[x].l].sum+tree[tree[x].r].sum;
tree[x].cnt=tree[tree[x].l].cnt+tree[tree[x].r].cnt;
}
int Sum(int x,int y,int l,int r,int L,int R){
if(L>R) return 0;
if(L<=l&&r<=R){
return tree[x].sum-tree[y].sum;
}
int mid=(l+r)>>1,res=0;
if(L<=mid) res+=Sum(tree[x].l,tree[y].l,l,mid,L,R);
if(R>mid) res+=Sum(tree[x].r,tree[y].r,mid+1,r,L,R);
return res;
}
int Cnt(int x,int y,int l,int r,int L,int R){
if(L>R) return 0;
if(l>r) return 0;
if(L<=l&&r<=R){
return tree[x].cnt-tree[y].cnt;
}
int tmp=tree[tree[y].l].cnt-tree[tree[x].l].cnt;
int mid=(l+r)>>1,res=0;
if(L<=mid) res+=Cnt(tree[x].l,tree[y].l,l,mid,L,R);
if(R>mid) res+=Cnt(tree[x].r,tree[y].r,mid+1,r,L,R);
return res;
}
int Ge(int x){
++x;
return x*(x-1)/2;
}
signed main(){
n=read();Qt=read();
for(int i=1;i<=n;i++) a[i]=read();
for(int i=1;i<=n;i++) xo[i]=xo[i-1]^a[i];
for(int i=0;i<=31;i++) S[i][0]=S[i][1]=n+1;
for(int i=n;i>=1;i--){
rig[i]=n+1;
for(int j=0;j<=31;j++) rig[i]=min(rig[i],S[j][(xo[i-1]>>j)&1]);
rig[i]--;
for(int k=31;k>=0;k--)
if(((xo[i-1]>>k)&1)^((xo[i]>>k)&1)){
S[k][(xo[i]>>k)&1]=i;
break;
}
}
for(int i=1;i<=n;i++) insert(rt[i],rt[i-1],1,n,rig[i]);
Q=read();
while(Q--){
int x,y,l,r;
x=read();y=read();
x=(x+ans*Qt)%n;y=(y+ans*Qt)%n;
x++;y++;
l=min(x,y);r=max(x,y);
ans=Sum(rt[r],rt[l-1],1,n,l,r)+Cnt(rt[r],rt[l-1],1,n,r+1,n)*r-(Ge(r)-Ge(l-1))+(r-l+1);
write(ans);putchar('\n');
}
return 0;
}