SnackDown 2017 Online Elimination Round Prefix XOR
题目传送门
题意
给出n个数，定义上升为a_ileq 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_ileq r。 即： 如果sum_r quad xor quad sum_{i-1}> sum_{r 1} quad xor quad sum_{i-1} rig_ileq 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)
代码语言：javascript复制#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 '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;
}
