SnackDown 2017 Online Elimination Round Prefix XOR
SnackDown 2017 Online Elimination Round Prefix XOR
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位其实就有了限制，易得： (二进制下)
- sum_r的第k位为0，那么sum_{i-1}的第k位必须是1。
- sum_r的第k位为1，那么sum_{i-1}的第k位必须是0。
那么我们可以倒序枚举i,记录S[j][0/1]表示当前第j位限制为0/1时的位置，那样就可以快速求出rig_i了。 如果[l,r]不存在rig_i>rrig_i-i+1(l \leq i \leq r 且 rig_i \leq r)，但如果存在rig_i>rr-i+1(l \leq i \leq r 且 rig_i > r)
#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;
}