P7003 [NEERC2013]Hack Protection

25 Nov 2020 1490字 5分 21次位运算
如果这篇博客帮助到你，可以请我喝一杯咖啡~
CC BY-NC-SA 4.0 （除特别声明或转载文章外）

首先，将一个数与上另一个数，这个数 1 的数量不增，所以当左端点固定时，区间的与和最多只有 $\log$ 种取值。

对于与和相同且左端点固定的区间，我们只需要在 $O(\log)$ 的时间内找到其中有多少个区间异或和等于这个固定的与和即可，设区间端点为 $l,r$ 。

我们求出原数列的异或前缀和，设为数列 $b$ ，则 $\oplus_{i=l}^ra_i=b_r\oplus b_{l-1}$ ，设与和为 $x$ 我们求的就是 $\sum\limits_{i=l}^r[b_i\oplus b_{l-1}=x]=\sum\limits_{i=l}^r[b_i=b_{l-1}\oplus x]$ ， $b_{l-1}\oplus x$ 当区间固定时是定值，所以问题被转化为经典问题，求区间内给定数的出现次数，由于询问次数是 $O(n\log a_i)$ 所以我们要在 $O(\log)$ 内完成查询，使用 vector 里二分或主席树均可。

总复杂度 $O(n\log a_i\log n)$

代码

#include<cstdio>
#include<vector>
#include<algorithm>
std::vector<int> v[100010];
int lg[100010],a[100010][18],b[100010],n,qcnt,c[100010];
long long ans;
int query(int const &l,int const &r){
	int k=lg[r-l+1];
	return a[l][k]&a[r-(1<<k)+1][k];
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",a[i]),c[i]=b[i]=b[i-1]^a[i][0];
	std::sort(c+1,c+n+1);
	for(int i=1;i<=n;i++)b[i]=std::lower_bound(c+1,c+n+1,b[i])-c,v[b[i]].push_back(i);
	for(int i=2;i<=n;i++)lg[i]=lg[i>>1]+1;
	for(int j=1;j<=lg[n];j++)
		for(int i=1;i+(1<<(j-1))<=n;i++)
			a[i][j]=a[i][j-1]&a[i+(1<<(j-1))][j-1];
	for(int i=1;i<=n;i++){
		int l=i,r=i;
		for(;l<=n;l=r+1){
			int ll=l,rl=n,mid=0,res=query(i,l);
			while(ll<=rl){
				mid=(ll+rl)>>1;
				if(query(i,mid)!=res) rl=mid-1;
				else ll=mid+1,r=mid;
			}
			int ord=res^c[b[i-1]];
			int p=std::lower_bound(c+1,c+n+1,ord)-c;
			if(p<=n&&c[p]==ord)
				ans+=std::upper_bound(v[p].begin(),v[p].end(),r)-std::lower_bound(v[p].begin(),v[p].end(),l);
		}
	}
	printf("%lld\n",ans);
	return 0;
}

P7003 [NEERC2013]Hack Protection gxy001

代码