SnackDown 2017 Online Elimination Round Prefix XOR

(Updated: )
oi
, ,

题目传送门

题意

给出$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;
}