「2017 山东二轮集训 Day1」第一题

发表于
字数统计: 1,410字 | 阅读时长 ≈ 7min

「2017 山东二轮集训 Day1」第一题

题目描述

小火车沉迷垃圾手游不能自拔，正在玩碧蓝航线，可惜小火车的舰（lao）队（po）练度太低打不过副本，所以他只好去刷其余的副本来升级。

总共有 $ n $ 个副本编号从 $ 1 $ 到 $ n $，每个副本有个难度值 $ a_i $，小火车每天按照顺序刷连续的一段副本，第 $ j $ 天会刷的副本必须落在 $ l $ 到 $ r $ 之间。但是他是个很懒的人，每天一开始他的懒惰值为 $ 0 $，当他刷完一个副本以后懒惰值就会异或上 $ a_i $，小火车希望懒惰值一直保持单调不下降，请问每天他都有多少种刷副本的方法？

输入格式

第一行一个整数 $ n $，表示副本数量。
接下来一行 $ n $ 个整数表示副本的难度。
接下来一行一个整数 $ m $ 表示天数。
接下来 $ m $ 行每行两个整数 $ a, b $ 表示一组询问，为了体现程序的在线性，题目中说的 $ l $ 和 $ r $ 都需要计算得到，设上个询问的答案为 $ \text{lastAns} $（初始为 $ 0 $），则 $ l = (( a + \text{lastAns}) \bmod n) + 1, r = ((b + \text{lastAns}) \bmod n) + 1 $，当然如果这样求得的 $ l $ 和 $ r $ 满足 $ l > r $ 请将 $ l $ 和 $ r $ 交换。

输出格式

$ m $ 行每行一个整数表示答案。

数据范围与提示

对于 $ 20\ %$ 的数据 $ n, m \leq 5000 $，数据随机；
对于另外 $ 20\% $ 的数据 $ m = 1, l = 0, r = n - 1 $；
对于另外 $ 30\% $ 的数据随机；
对于 $ 100\% $ 的数据 $ n, m \leq 100000, 0 \leq a_i \leq 10 ^ 9 $。

显然从某天开始的刷副本方案的右端点构成一段连续区间。只要对于每个位置都求出它对应的区间的右端点就可以统计答案了。这里统计答案采用主席树，第$i$棵树维护的是$[1,i]$天对应的区间。由于是要支持区间修改的主席树，注意下放标记时新建节点这样的细节。

暴力找右端点，然后这道题就做完了。我的暴力跑得比下面的方法还快= =

容易想到对于每个位置二分答案求右端点。

考虑对于懒惰值$x$,怎样的$a_i$会使得它降。显然只讨论$a_i$非$0$的情况，写出下面的表：

$x$ $0$ $1$ $0$ $1$
$a_i$ $0$ $0$ $1$ $1$
$ret$ $0$ $1$ $1$ $0$

发现$a_i$为$0$的位不会影响答案的合法性。容易发现从高位到低位讨论后，记$a_i$的最高位为第$k$位，那么不降当且仅当$x$的第$k$位是$0$。

所以用$cnt[i][j][0/1]$记录$a_1,a_2,..,a_i$的$i$个异或前缀和中，$j$作为$a$的最高位时最高位的$0/1$总个数。二分答案检查时每一位都验证一下就行了。

时间复杂度$O(nlognloga+mlogn)$。

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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include<stdio.h>
#include<algorithm>
#include<cstring>
#define ll long long
#define MAXN 100005
#define MAXT 20000005
using namespace std;

char *p1,*p2,buf[1<<20];
#define GC (p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?0:*p1++)
inline int _R(){
	char s=GC;int v=0;
	while(s>57||s<48)s=GC;
	for(;s>47&&s<58;s=GC)v=v*10+s-48;
	return v;
}

int N,M,A[MAXN],s[MAXN],cnt[MAXN][32][2];ll Ans;
int rt[MAXN],ls[MAXT],rs[MAXT],tot;
ll sum[MAXT],lazy[MAXT];

int clone(int p){
	int cp=++tot;
	ls[cp]=ls[p];rs[cp]=rs[p];sum[cp]=sum[p];lazy[cp]=lazy[p];
	return cp;
}

void update(int p){sum[p]=sum[ls[p]]+sum[rs[p]];}

void putdown(int p,int l,int r){
	if(l==r||lazy[p]==0){lazy[p]=0;return;}
	ls[p]=clone(ls[p]);rs[p]=clone(rs[p]);
	int mid=l+r>>1;
	sum[ls[p]]+=(ll)(mid-l+1)*lazy[p];
	sum[rs[p]]+=(ll)(r-mid)*lazy[p];
	lazy[ls[p]]+=lazy[p];
	lazy[rs[p]]+=lazy[p];
	lazy[p]=0;
}

void modify(int &p,int l,int r,int x,int y){
	if(!p)p=++tot;
	else putdown(p,l,r),p=clone(p);
	if(x<=l&&r<=y){sum[p]+=r-l+1;lazy[p]++;return;}
	int mid=l+r>>1;
	if(x<=mid)modify(ls[p],l,mid,x,y);
	if(y>mid)modify(rs[p],mid+1,r,x,y);
	update(p);
}

ll getsum(int a,int b,int l,int r,int x,int y){
	putdown(a,l,r);putdown(b,l,r);
	if(a==0&&b==0)return 0;
	if(x<=l&&r<=y)return sum[b]-sum[a];
	ll ret=0;int mid=l+r>>1;
	if(x<=mid)ret+=getsum(ls[a],ls[b],l,mid,x,y);
	if(y>mid)ret+=getsum(rs[a],rs[b],mid+1,r,x,y);
	return ret;
}

bool check(int l,int r){
	for(int i=0;i<=30;i++){
		if((s[l]>>i&1)!=(A[l]>>i&1)){
			if(cnt[r][i][1]-cnt[l][i][1])return false;
		}
		else if(cnt[r][i][0]-cnt[l][i][0])return false;
	}
	return true;
}

int hbit(int a){
	if(!a)return -1;
	for(int i=30;i>=0;i--)if(a>>i&1)return i;
}

int main(){
	int i,j,t,l,r,mid;ll tmp;
	N=_R();
	for(i=1;i<=N;i++)A[i]=_R(),s[i]=s[i-1]^A[i];
	for(i=1;i<=N;i++){
		memcpy(cnt[i],cnt[i-1],sizeof(cnt[i-1]));
		t=hbit(A[i]);
		if(t==-1)continue;
		cnt[i][t][s[i]>>t&1]++;
	}
	
	for(i=1;i<=N;i++){
		l=1;r=N-i+1;
		while(l<=r){
			mid=l+r>>1;
			if(check(i,i+mid-1))l=mid+1;
			else r=mid-1;
		}
		rt[i]=rt[i-1];
		modify(rt[i],1,N,i,i+r-1);
	}
	
	M=_R();
	while(M--){
		l=_R();r=_R();
		l=(ll)(l+Ans)%N+1;r=(ll)(r+Ans)%N+1;
		if(l>r)swap(l,r);
		Ans=getsum(rt[l-1],rt[r],1,N,l,r);
		printf("%lld\n",Ans);
	}
}